# Big O of two sum

**URL:** <https://forum.freecodecamp.org/t/big-o-of-two-sum/70331>\
**Category:** General\
**Created:** [December 29, 2016, 4:40pm UTC](https://forum.freecodecamp.org/t/big-o-of-two-sum/70331 "2016-12-29T16:40:30Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![carl-parrish](https://sea3.discourse-cdn.com/freecodecamp/user_avatar/forum.freecodecamp.org/carl-parrish/32/158754_2.png) [@carl-parrish](https://forum.freecodecamp.org/u/carl-parrish)\
**Post date:** [December 29, 2016, 4:40pm UTC](https://forum.freecodecamp.org/t/big-o-of-two-sum/70331/1 "2016-12-29T16:40:31Z")

</div>

#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:

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

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

```

Here is my solution.

```auto
/**
 * @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.

---

<div class="post-metadata">

**Author:** ![timotheap](https://sea3.discourse-cdn.com/freecodecamp/user_avatar/forum.freecodecamp.org/timotheap/32/26039_2.png) [@timotheap](https://forum.freecodecamp.org/u/timotheap)\
**Post date:** [December 29, 2016, 5:01pm UTC](https://forum.freecodecamp.org/t/big-o-of-two-sum/70331/2 "2016-12-29T17:01:28Z")

</div>

You should put your topic in ‘Help’ not in ‘Project feedback’ as it’s about algorithms

---

<div class="post-metadata">

**Author:** ![kevcomedia](https://sea3.discourse-cdn.com/freecodecamp/user_avatar/forum.freecodecamp.org/kevcomedia/32/125737_2.png) [@kevcomedia](https://forum.freecodecamp.org/u/kevcomedia)\
**Post date:** [December 30, 2016, 1:22am UTC](https://forum.freecodecamp.org/t/big-o-of-two-sum/70331/3 "2016-12-30T01:22:12Z")

</div>

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).

---

<div class="post-metadata">

**Author:** ![carl-parrish](https://sea3.discourse-cdn.com/freecodecamp/user_avatar/forum.freecodecamp.org/carl-parrish/32/158754_2.png) [@carl-parrish](https://forum.freecodecamp.org/u/carl-parrish)\
**Post date:** [December 31, 2016, 9:01pm UTC](https://forum.freecodecamp.org/t/big-o-of-two-sum/70331/4 "2016-12-31T21:01:45Z")

</div>

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)?

---

<div class="post-metadata">

**Author:** ![jmcilhargey](https://sea3.discourse-cdn.com/freecodecamp/user_avatar/forum.freecodecamp.org/jmcilhargey/32/24702_2.png) [@jmcilhargey](https://forum.freecodecamp.org/u/jmcilhargey)\
**Post date:** [December 31, 2016, 11:39pm UTC](https://forum.freecodecamp.org/t/big-o-of-two-sum/70331/5 "2016-12-31T23:39:17Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![kevcomedia](https://sea3.discourse-cdn.com/freecodecamp/user_avatar/forum.freecodecamp.org/kevcomedia/32/125737_2.png) [@kevcomedia](https://forum.freecodecamp.org/u/kevcomedia)\
**Post date:** [December 31, 2016, 11:43pm UTC](https://forum.freecodecamp.org/t/big-o-of-two-sum/70331/6 "2016-12-31T23:43:22Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![jwilkins.oboe](https://sea3.discourse-cdn.com/freecodecamp/user_avatar/forum.freecodecamp.org/jwilkins.oboe/32/179497_2.png) [@jwilkins.oboe](https://forum.freecodecamp.org/u/jwilkins.oboe)\
**Post date:** [January 16, 2021, 6:11am UTC](https://forum.freecodecamp.org/t/big-o-of-two-sum/70331/7 "2021-01-16T06:11:26Z")

</div>

Closed on January 16, 2021, 6:11am UTC