# Big-O Intro

Given a target (say, 10) and an array of numbers, we are asked to find if any two numbers in the array add up to 10.

Most beginner programmers (me) would come up with an algorithm that involves a nested loop. We start with the array’s first number, then check it against each successive array element to test whether they add up to 10. If none do, we then take the second array element and perform the same checks. This process continues — first loop establishes an anchor number, second loop checks the anchor against all possibilities — until we’ve either found a match and returned `true`

or we’ve checked and rejected all the possibilities and returned `false`

.

In code:

This nested loop would be considered *Big-O of n squared* — efficient and therefore undesirable.

So how can we make this more efficient?

Well, if we knew the given array of numbers was sorted we can (potentially, depending on the array elements) achieve *Big-O of n* by eliminating the need for the nested `for`

loop. Like this:

Line-by-line breakdown:

- Line 2: initialize pointer variable
`j`

to the array length — we will use`j`

to reference array elements starting from the back, or highest numbers. - Lines 3–11:
`for`

loop starting at the beginning of the array and continuing until the`for`

loop’s counter meets`j`

. - Line 4: initialize variable
`match`

— the number which, when added to the current array element, equals the given target. - Lines 5–10:
`while`

loop — when array element pointed to by`j`

(initially set to the array’s highest number) is greater or equal to`match`

- Lines 6–8: check if we have a match. If yes return
`true`

. - Line 9: decrement
`j`

. - Line 12:
`for`

loop has completed with no result, return`false`

.

Overall explanation:

The trick in the more efficient approach is to use a pointer variable then decrement it using a nested `while`

loop rather than nested `for`

loop. Using this approach, we can eliminate the need to check against array elements that are mathematically impossible.

Let’s walk through the execution:

`j`

is set to the amount of array elements so that when we reference `j`

using` movieDurations[j]`

we get the last element in the array, or the highest number since it's a sorted array. On the `for`

loop’s first iteration `match`

equals 9 (10 minus 1, where 1 is the initial array element referenced by `movieDurations[i]`

) and `movieDurations[j] `

equals 11. 11 satisfies the `while`

condition so we enter the `while `

loop. 11 is not 9, so we don’t return true. Then we decrement `j`

and start from the beginning of the `while`

loop. This time, `movieDurations[j]`

references the next highest element in the array, 8. 8 does not satisfy the `while`

loop’s condition, so we return to the beginning of the `for`

loop. `i`

is incremented to 1, so `movieDurations[i]`

now references 3 and `match`

now equals 7. Moving to the `while`

loop — `movieDurations[j]`

still references 8, which is greater than 7, so we enter the `while`

loop. 8 is not 7, so we decrement `j`

and return to the beginning of the `while`

loop. Now, `movieDurations[j]`

references 7, which satisfies the `while `

loop and is also equal to `match`

, so we return `true`

and finish executing.

So, the `while`

loop helps us determine whether there’s a potential match. If there is a match, great we’re done. If not, we can skip right along to the next `for`

loop iteration without checking array elements we know wont work.

Using this approach, we’ve avoided the need to execute nested `for`

loops which would check each successive array element. Rather, we can target the potential matches by matching up the lowest/earliest elements with the highest/latest elements. Basically, this speeds things up.

If you compare the actual runtimes of the two approaches the difference seems negligible. And it is, given our small array. But what if that array contained 1000s, or 100000s of elements? Then we are talking some serious time-saving.