3_big_O.md

Useful resources

Note: The Python solutions to exercises can be found in these repos:

Big-O cheat sheet

What is good code?

1. Readable
2. Scalable: In terms of Speed (time complexity) and ***memory (space complexity)***. There’s usually a tradeoff between speed and memory.

Note: Big-O is what allows us to measure code scalability. Big-O is the language we use for talking about how long an algorithm takes to run. In here, we care about large inputs (the end of the graphs).

We can compare two different algorithms and say which one is better than the other when it comes to scale, regardless of our computer differences.

$\large{\textbf{Data Structure + Algorithms = Programs}}$

source

Time complexity

What’s the big-O of the following scripts?

function funChallenge(input) {
  let a = 10;
  a = 50 + 3;

  for (let i = 0; i < input.length; i++) {
    anotherFunction();
    let stranger = true;
    a++;
  }
  return a;
}

Answer: O(n)

function anotherFunChallenge(input) {
  let a = 5;
  let b = 10;
  let c = 50;
  for (let i = 0; i < input; i++) {
    let x = i + 1;
    let y = i + 2;
    let z = i + 3;

  }
  for (let j = 0; j < input; j++) {
    let p = j * 2;
    let q = j * 2;
  }
  let whoAmI = "I don't know";
}

Answer: O(n)

Big-O rules

Rule 1: Always considering the worst-case scenario.

const nemo = ['nemo', 'nemo2', 'nemo3'];

function findNemo1(array) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === 'nemo') {
      console.log('Found NEMO!');
      break;
    }
  }
}

findNemo1(nemo);

Note: In the above example, although nemo is the first element in the array and the function finds it after only 1 iteration (i.e. O(1)), but it doesn’t matter because the worst-case scenario here is that nemo being the very last element in which case the big-O will be O(n).

Rule 2: Always remove the constants.

function printFirstItemThenFirstHalfThenSayHi100Times(items) {
    console.log(items[0]);

    var middleIndex = Math.floor(items.length / 2);
    var index = 0;

    while (index < middleIndex) {
        console.log(items[index]);
        index++;
    }

    for (var i = 0; i < 100; i++) {
        console.log('hi');
    }
}

Note: If we go line by line in the function above, we get O(1 + n/2 + 100), which simplifies to O(n), because it’s still linear.

Rule 3: Different terms for inputs.

function compressBoxesTwice(boxes) {
	boxes.forEach(function(boxes) {
		console.log(boxes);
	});

	boxes.forEach(function(boxes) {
		console.log(boxes);
	});
}

Note: The example above is O(2n) which is O(n). But if we have two inputs (like the example below), the big-O is no longer O(n). We have to consider both input sizes, therefore it is O(n + m).

function compressBoxesTwice(boxes, boxes2) {
	boxes.forEach(function(boxes) {
		console.log(boxes);
	});

	boxes2.forEach(function(boxes) {
		console.log(boxes);
	});
}

Note: The example below shows a nested loop which is a $\mathbf{O(n^2)}$ , i.e. $\mathbf{O(n*n)}$

const boxes = ['a', 'b', 'c', 'd', 'e'];
function logAllPairsOfArray(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length; j++) {
      console.log(array[i], array[j])
    }
  }
}

logAllPairsOfArray(boxes)

Rule 4: Drop non-dominant terms.

function printAllNumbersThenAllPairSums(numbers) {

  console.log('these are the numbers:');
  numbers.forEach(function(number) {
    console.log(number);
  });

  console.log('and these are their sums:');
  numbers.forEach(function(firstNumber) {
    numbers.forEach(function(secondNumber) {
      console.log(firstNumber + secondNumber);
    });
  });
}

printAllNumbersThenAllPairSums([1,2,3,4,5])

Note: The above example is $\mathbf{O(n + n^2)}$ . If we drop the non-dominent term it becomes $\mathbf{O(n^2)}$ .

Note: The O(n!) is the most inefficient. It basically means for every input we add a nested loop. This is probably the most trivial example of a function that runs in O(n!) time (where n is the argument to the function):

void nFacRuntimeFunc(int n) {
  for(int i=0; i<n; i++) {
    nFacRuntimeFunc(n-1);
  }
}

Space complexity

When a program executes, it has to ways to remember things:

Heap: is usually where we store variables that we assign values to.
Stack: is usually where we keep track of our function calls.

In space complexity, we simply look at the total size relative to the size of the input and see how many additional new variables (or new memory) we’re allocating. In that sense, the size of the input doesn’t matter (because we can’t do anything about it). What we care about is what additional space we’re requiring in our code.

What causes space complexity?

Adding variables
Data structures
Function calls
Allocations

//#5 Space complexity O(1)
function boooo(n) {
    for (let i = 0; i < n; i++) {
        console.log('booooo');
    }
}

// #6 Space complexity O(n)
function arrayOfHiNTimes(n) {
    var hiArray = [];
    for (let i = 0; i < n; i++) {
        hiArray[i] = 'hi';
    }
    return hiArray;
}

arrayOfHiNTimes(6)

Example: Twitter
Let’s say you’re working at Twitter and you’re asked to build a feature that allows anybody to click a button next to their name and retrieve their most recent tweet and their oldest tweet.

We don’t know if the tweets are sorted (so can’t go by picking the first and last element of array).
We gotta compare tweets to each other based on dates which is a $\mathbf{O(n^2)}$ (nested loop).