Algorithm Complexity

Head – O(1) grows like 2x input size x running time

List Items – O(n) – more scalable, less time

O(n2) –

“Quadratic time complexity”

3 nest for loops ~ O(n3)

Binary search

array = [ 1,2,3,4,5,6,7,8,9,10 ]
Search for 3 takes 3 steps
Search for 9 takes 3 steps

Even if we double the input we only add 1 step
array = [ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 ]

This is the most durable to change
O(log n) – faster than a linear algorithm

Example of O(n)

function solution(k, arr){
    var map = {};
    for (var i=0; i < arr.length ; i++){
        var tmp = k - arr[i];
        if (temp > 0 && map[tmp] == 1)
            console.log("Found the pair :", temp, arr[i]);
        else
            map[arr[i]] = 1;
    }
}

Technical Debt = using bad code or inefficient code now saying you will fix it later.

# Big O Analysis

Express the running times of the following algorithms in Big O notation. Justify your responses.

Some of these are just review. A few apply Big O to algorithms we saw before.

Assume the _worst case_ running time—i.e., consider only the _maximum_ number of instructions the algorithm could take.

What is the running time of…

* Selection sort?

* Insertion sort?

* Linear search?

* Binary search?

* Finding duplicates in an array?

### BONUSES

If you’re mathematically inclined, you might find these interesting. If not, feel free to take a stab anyway, but don’t worry too much about proving your solution.

What is the running time for an algorithm that—

* Finds all triplets `(x, y, z)` such that `x + y + z = n`, where `n` is specified by the user?

* E.g.: `threeSum(list, search)` will find all possible triplets of numbers in `list` that sum to `search`.

* Same question, but for doubles?

* In general, what is the running time for finding n-tuples in `list` that sum to `search`?