# Big O of two sum

#Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

##Example:

``````Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
``````

Here is my solution.

``````/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
return nums.reduceRight((ans,val,idx,arr)=>{
const remainder =  target - val;
const idx2 = arr.indexOf(remainder);
return (idx !== idx2 && idx2 !== -1)?[idx, idx2]: ans;
},[]);
``````

Iâm thinking this is the best answer because O(n) but would like feedback.

You should put your topic in âHelpâ not in âProject feedbackâ as itâs about algorithms

2 Likes

I donât think itâs O(n), but O(n2) in the worst case, because of the `.indexOf()` call in the callback (I assume `.indexOf` is O(n) in the worst case).

2 Likes

I guess Iâve been assuming .indexOf() was working at something better than O(n) but even so wouldnât it be O(n) + O(n) and not O(n) * O(n)?

Anytime you have to search through a dataset of n, the runtime will be O(n). If for each element in the dataset you have to search through the dataset again, then itâs O(n^2). So in this case where for every element, youâre searching the array to find if there is a matching element such that a + b = target, it would be O(n^2). Thereâs a way to do it in O(n) using whatâs called a âgreedyâ approach where you keep track of what youâve seen as you iterate through the array so when you come upon a number that matches the condition a + b = target you return that number. Hint, youâll need to use additional space to store the values youâve seen. Is O(n) the best we could do? Yes because we know that we may have to look at every element in the array to get the answer.

1 Like

I came up with O(n2) because I think youâre calling `.indexOf` (which I assume to be O(n) in the worst case) at most n times, like in a nested loop

1 Like