We all need a way to measure the performance (efficiency) of our algorithms as they scale up. We can perform an analysis on the efficiency by considering the number of resources, in our case,time andspace.

Thespace used is determined by the number and sizes of variables together with the data structures being used. Thetime is determined by the elementary operations that must be performed during the algorithm execution.

In this article we will be going over time and space complexities and how the Big O notation is a standard measure of complexity.

That said, thetime to run our algorithms ishighly dependent on the software and hardware environment they run in. They are influenced by factors such as:

• Read/Write Speed
• Number of programs running
• RAM size
• Processor type
• Machine configuration
• Compilers or libraries being used

We therefore need a methodology that isindependent of the software and hardware environment that takes into account all possible inputs.

This is done by ahigh-level description of the algorithm by associating each algorithm with a functionf(n) that characterizes the running time of the algorithm in terms of the input sizen.

Given the functionsf(n) andg(n), we do say thatf(n) is Big O of g(n) being written as:

f(n) is O(g(n))

Therefore Big O, (pronounced as Big Oh), describes how well the performance of our algorithms are as the input data grows larger.

It assists us in knowing which algorithm suits which task, and which one is not by estimating the different runtimes of the algorithms. The estimation of how the runtime varies with the problem size is called theruntime complexity of an algorithm.

A simple example of how different algorithms use different runtime complexities, is a tale of a South African telecommunication company with a slow network speed and a pigeon. The company wanted to send some information to its other office which was 50 miles away.

The information was given to both using data signals and an envelope respectively. Ironically, the pigeon delivered the data ahead of the telco network. Here, the pigeon could deliver any amount of information whether too large or too little at the same constant duration while the network's delivery time was inversely proportional to the amount of information being sent.

There are many notations of Big O but here we are going to discuss a few of them which are:

• O(1)
• O(n)
• O(n²)
• O(log₂n)

In the article, we will also estimate the Big O of a sample algorithm.

In the code examples, we will use Python for illustrations but you can rewrite them using a language of your choice.

1. O(1) Constant runtime complexity

This means that the algorithm does a fixed number of operations no matter the number of inputs.

Let's look at the code snippet below:

deffirst_element(array):print(array[0])

The functionfirst_element() takes an array passed in and prints the first element and does not consider how many elements are present in the array.

Take a look at the graph representation below:

O(1) graph
Image Source

2. O(n) Linear runtime complexity

This means that the runtime complexity of your algorithm increases linearly with the size of the input data.

Example:

defshow_array_elements(array):foriinrange(len(array)):print(array[i]+"\n")

The code takes in an array using the functionshow_array_elements() and displays the array elements.
If the array passed in as an argument only has1 element, then the algorithm will only take1 operation to run and would similarly take300 operations for an array with300 elements. The number of times the loop iterates depends on the number of array elements.

O(n) graph
Image Source

3. O(n²) Quadratic runtime complexity

The algorithm varies with the square of the problem size, n.

Example:

defadd_array_elements(array):sum=0foriinrange(len(array)):forjinrange(len(array)):sum+=array[i]+array[j]returnsum

The code has two loops, theouter, and theinner. The outer loop iterates n times giving an element to the inner loop which again loops n times, per one loop of the outer array, adding the element given by the outer array and all the array elements.

Taking a case where the array has 3 elements; the outer loop takes 3 operations in total to iterate over each element. For every 3 operations of the outer loop, the inner loop also takes 3 operations to iterate over each element. That is 3 × 3 operations amounting to 9.

O(n²) graph
Image Source

4. O(log₂n)- Logarithmic runtime complexity

This is associated with the binary search algorithm that searches by doing necessary halvings to get the item being searched for. The essence of this method is to compare the value being searched for, let's name itX, with the middle element of the array and if X is not found there.

We then decide which half of the array to look at next, which is repeated until X is found. The expected number of steps depends on the number of halvings needed to get from n elements to 1 element.

Have a look at the code and graphical illustrations below:

defbinary_search(array,query):lower_bound=0upper_bound=len(array)-1found_bool=Falsewhile(lower_bound<=upper_boundandfound_bool==False):middle_value=(lower_bound+upper_bound)//2ifarray[middle_value]==query:found_bool=Truereturnfound_boolelifquery>array[middle_value]:lower_bound=middle_value+1else:upper_bound=middle_value-1returnfound_boolarray=[1,2,3,4,5,6,7,8,9]query=7val_found=binary_search(array,query)

Step 1
The code takes in a sorted array with 9 elements through the functionbinary_search() and searches for the value, the parameter namedquery, 7. It divides it in half and checks if 7 is in the middle.

Step 2
The middle value is 5 and our algorithm checks it with 7 and since 7 is greater than 5, then it will move to the right-hand side.

Step 3
We now have an array with 4 elements. The algorithm will divide it by half to get two arrays with 6 & 7 and 8 & 9.
The one with 8 & 9 will be ignored and the algorithm will now check and compare 6 and 7.

Step 4
The comparison will be done and we will arrive at 7.

Further example inputs and themaximum number of steps to be taken are shown in the table below:

O(log₂n) graph
Image Source

Determining the Big-O of an algorithm

Here we look at the best-case and worst-case scenarios.

Best and worst-case scenarios

We will base our inferences based on the code below:

deflinear_search(array,query):foriinrange(len(array)):ifarray[i]==query:returnireturn-1defbinary_search(array,value):lower_bound=0upper_bound=len(array)-1found_bool=Falsewhile(lower_bound<=upper_boundandfound_bool==False):middle_value=(lower_bound+upper_bound)//2ifarray[middle_value]==value:found_bool=Truereturnfound_boolelifvalue>array[middle_value]:lower_bound=middle_value+1else:upper_bound=middle_value-1returnfound_boolarray=[1,2,3,4,5,6,7,8,9]value=7

The best case forlinear_search() would be finding the value 1, O(1), while the worst case would be finding the last array element or a value not included in the array O(n). This is because it needs to traverse each element giving an O(n) complexity.

The best case for thebinary_search() would be searching for the value of 5, which is the value in the middle of the array O(1). The worst-case would be searching the value 1 or 10, the first and the last elements of the array, or a value not included in the array. This is because the algorithm needs to make the halvings necessary until it reaches the first and the last elements (O(log₂n)).

Checking the Big O of a sample code

We will look at the worst-case scenario perspective.

We will estimate the Big O of the code below (we are simply estimating its complexity, no conditional checks have been put for the code):

defarray_arithmetic(array):value=0# O(1) complexityforeinrange(len(array)):# O(n) complexityforjinrange(10):# O(10) complexityforkinrange(len(array)//2):# O(n/2) complexityvalue+=array[e]+array[j]+array[k]# O(1) complexityreturnvalue# O(1) complexity

We should start with the innermost loop.

1. The innermost loop hasO(n/2) complexity while its operation hasO(1) complexity. The innermost loop therefore has(n/2) * (1) complexity.

2. The second inner loop has O(10) complexity and the inner loop (in No. 1) of this loop hasO(n/2) meaning the whole second inner loop has(10) * (n/2) = O(5n) complexity.

3. An outer loop hasO(n) complexity. The inner loop (No. 2) of this outer loop has in totalO(5n) complexity.
   So, they haven*5n = 5n² complexity.

4. Combining the loop's complexity together with the two operations outside the loop, we get1+1+5n² = O(2+5n²).

We drop all constants when estimating the Big O notation in that we remain with O(n²) instead ofO(2+5n²).

The code above therefore hasO(n²) complexity.

That's all for now. Hope you will consider the scalability of your algorithm next time you write one.

Happy Coding!