Big O Notation Explained

Big O Notation Explained…

Many of my younger friends in programming often act like they are in an advanced math class when programmers start throwing expressions around like (O(n), O(!n), O(Log n), etc. In fact in most programming job interviews these days, you will be asked to solve a programming challenge, with constraints that come in the way of Big O notation.

By the time you are done reading this article, you will find its not as difficult as it sounds.

So What is Big O Notation?
Big o notation is simply a means of measuring the space and time resources the computer expends while executing a task.

For instance, if you write a program that simply loops through an array, the computer will have to touch each element in the array while executing the program. Thus, we say that such an algorithm has O(n) time constraint because the computer will spend time crunching each element in the array. The n in this expression represents the length of the array.

In other words, for every task the computer executes, there is always a question of how much time (and space) it will take the computer to finish this task. Such question can be answered using Big O Notation.

Some Big O notation representations explained.

O(1)
Also known as constant time complexity, this is the most efficient runtime in time space complexity. when you see this formula, it means that the computer, in executing the task in question, will take the same amount of time to execute the task, regardless of whether the input length is 1, or 1000000.

An example of a task that will take O(1) time space complexity.

Given an array of 1billion elements, return its first element.

Solution (javascript):

function returnFirstElementInArray(arr){

return arr[0];
}

As you can see in the example, the function does not do any checks, it touches only the first element in the array. Even if the question was changed to given an array of 10 elements, the function will execute in the same amount of time. Thus, this function requires O(1) time complexity.

O(n)
This is also known as linear runtime. When you see this formula, it means that the computer in executing the task in question, will touch every element, in its input data.

An example of a task that will take O(n) time space complexity is

Given an array, return the biggest digit in the array

Solution

function returnBiggestDigitInArray(arr){

var biggestDigit = arr[0];

for(var i = 0; i < arr.length; i++){

if( arr[i] > biggestDigit){
biggestDigit = arr[i]
}
}

return biggestDigit;
}

In executing the above function, the computer will touch all the elements in the array so we say it takes O(n) runtime. n in this case represents the length of the array.

O(n) algorithms are fast when the input dataset is small. But gets slower as the input dataset gets bigger.

O(Log n)
This means that it takes the logarithm of n time complexity to execute the task. It is best examplified by divide and conquer alorithms a classic example of which is searching a sorted array.

Example task:
Given a sorted array, and a digit, return the index of that digit in the array.
E.. for input 1,4,5,6,19,20 find t the index of 2 in the input.

Solution (javascript)
private static int getIndexInArray(arr, digit, start, middle, end){

if(digit == arr[middle]){
return middle;
}

if(digit == arr[start]){
return start;
}

if(digit == arr[end]){
return end;
}

if(digit >arr[middle]){
start = middle;
middle = (start+end)/2;
return getIndexInArray(arr, digit, start, middle, end);
}

end = middle;
middle = ((start+end)/2);
return getIndexInArray(arr, digit, start, middle, end);

}

The solution above, divides the input by half every time the function is called recursively. And thus, the solution executes in O(Log n). O(Log n) algorithms are usually pretty efficient. In fact, they are more efficient than O(n) algorithms but not as efficient as O(1) algorithms most of the time.

O(n^2)
This is where things start to get really time consuming. O(n^2) means that in executing this task, the computer will go through every element in the array, as many times as the length of the array. A classic example is bubble sort algorithm as shown in the task below:

Given an unsorted array {30, 2, 4,1,6, 8, 2}, sort it using the bubble sort algorithm.

Solution (javascript)
private static int[] BubbleSort(int[] arr){
for(int i = arr.length-1; i >=0 ; i–){
for(int j = arr.length-1; j >=0 ; j–){
if(arr[i] > arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}

These are some of the primary Big O Notations every programmer should be acquainted with. There are others of course but for most interview questions and algorithm based projects, the above normally suffices.