Big O, oh what a dilemma you cause!

algorithm Aug 27, 2020

What is this Big O notation?

Big O is basically a not so boring math to measure effciency of code.
You will hear programmers use this language to talk about how efficient an algothm is or how long it will take for the algorithm to run.
To make it easy for now think of it as a measurement of how fast your code will run based on the input you give to it.

Let's look at some examples to make things clear.

Examples:

function printOne(items) {
    console.log(items);
}

Here if the input is 1 or 10000 the function will run only once. That means it has a run time of constant time. So relative to the input the Big O for this function is? Say with me, O of 1, or O(1).

function printList(list) {
    list.forEach(item => {
        console.log(item);
    }
}
    

Notice here we are looping over the input elements. So if there are 10 elements we will print 10 times, if there are 10000 element we will print 10000 times. The run time in this case is linear. So relative to the input the Big O for this function is O(n).

What if you have a function where you are looping over a list of items that has constant size? What will be the run time of the function in that case?

function printList(list) {
    // list will only ever have 10 elements
    list.forEach(item => {
        console.log(item);
    }
}

In this case we are only ever looping through 10 items so the runtime for this function is O(1), which again is constant time.

The constant must go

While computing the Big O you are only concerned about the worst case, so you can safely ignore the constant and less significant ones.

function printList(list) {
    console.log(list); // O(1)
    for(let i = 0; i< 10; i++) {
        console.log(i);
    } // O(1)
    list.forEach(item => {
        console.log(item);
    } // O(n)
}

Here the big O will be O(n + 2). But we can just remove the constant and the run time becomes O(n).

Similarly if you run across a scenario where the runtime is O(n+n^2) we can safely say it will be O(n^2).

Space Complexity

Like time complexity we might want to keep the memory usage to a minimum as well. Talking about memory cost (or "space complexity") is very similar to talking about time cost. We simply look at the total size (relative to the size of the input) of any new variables we're allocating.

function print(n) {
  for (let i = 0; i < n; i++) {
    console.log('Hello World');
  }
}

The above function takes up O(1) space, since it does not use any new memory to run.

function printList(n) {
  const arr = [];
  for (let i = 0; i < n; i++) {
    arr[i] = 'hello world';
  }
  return arr;
}

The above function takes up O(n) space, since it allocates a new array.

Sometimes you can't have it all. You must choose which one you want to save, space or time. It largely depends on your use case and your resources.

Lastly

Get in the habit of thinking about time and space complexity. This should become a second nature to you. All we want to do is become great developers, and to do that all we need to do is practice!

Happy Coding!