Big O Notation for Coding Interviews Explained Fast

This definition from Wikipedia elegantly explains big O in computer science as a classification of algorithms according to how their run time or space requirements grow as the input size grows.

It is an asymptotic analysis which implies that it is input bound. It calculates the worst-case scenario of an algorithm based on input, bounded by time and space.

The calculation for time and space is similar. In this explanation, we calculate the big O notation for time.

We would explain how to identify O(1), O(log(N)), O(N), O(N^2). It is worthy to note that the algorithms are arranged in terms of their time performance in the previous sentence.

For example, we calculate the time complexity of 3 algorithms with a given array input below:

a = [...] where array size nWe have three algorithms that take array 'a' as input and returns values.F1(a) => 1 + a[0]; algorithm F1 returns 1 plus the first array value of 'a'F2(a) => sum(a); algorithm F2 returns the sum of array value 'a'F3(a) => pair(a); algorithm F3 returns the pairing of the array values in 'a'.for example if a = [1,2,3], F3 returns 1,2  1,3  2,1  2,3...

If the size of the array 'n' increases to 10,000,000, we find out that:

• F1 algorithm still runs in constant time as it refers to a pointer to a memory location O(1)
• F2 algorithm runs in linear time as the time taken increases proportionally to the size of 'n' array O(N)
• F3 algorithm would most likely have a nested for loop that would mean it runs in O(N^2)

Logarithms in Big O

The expression log (n) = y in computer science assumes log is in base 2 and not base 10 like mathematics. This is a very important distinction to make. Therefore the full expression is log2 (n) = y.

To get 'n' we simply do 2^y = n. That means to get 'n' in log (n)=4, we simply do 2^4 = 16.

How to Identify O(log(N)) algorithms
Remember that in computer science the expression log (n) = y evaluates to log2 (n) = y, log is in base 2. Thus an expression log (n)=4 which can be solved as 2^4 = 16 simply multiplies 2 four times 2*2*2*2.

If we added 1 to 2^4+1 we would get 16*2 which is2^5=32

It means that the complexity of an operation when 1 is added to the given power is double the last value. The magic happens here!

To understand if a notation is O(log(N)), if we have an algorithm that keeps cutting an array in half like a binary search as shown below:

[0,1,2,3,4,5,6,7,8,9][0,1,2,3,4, | 5,6,7,8,9] => [0,1,2,3,4][0,1,2 | ,3,4] => [0,1,2][0,1 | ,2] => [0,1][0 | 1] => [0]

Or if it cuts a tree data structure in half. Read about tree data structure here, it is most likely a O(log(N)).