# Is my answer O(n2) runtime or O(n) runtime?

• public class Solution {
public int[] twoSum(int[] nums, int target) {
for(int x=0; x<nums.length-1; x++){
for(int y=x+1; y<nums.length; y++){
if(nums[x]+nums[y]==target){
int[] data = {x+1,y+1};
return data;
}
}
}
return null;
}
}

• This is worst case O(n^2). You're not technically doing n^2 calculations (really more like n^2 - (n(num[1] + num[last])/2)), but following big-Oh convention, you drop the lower magnitude factors.

• Format code properly for others to see your code.
Anyway, it should be obvious to you it's O(n^2) algorithm when you have two nested for loops (it doesn't matter even if you scan half of the matrix by making y=x+1. O(n^2)/2 is still O(n^2)

• thanks, i dont understand yet how could know what runtime is, any book that you recommend for this?

• Google is your guide! Try something like Big-O complexity, Algorithm complexity analysis etc.

http://discrete.gr/complexity/

http://bigocheatsheet.com/

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.