Okere chinedu Victor
chinedu | ddevguys

chinedu | ddevguys

Big(O) Notation summarized!

A summary of the big(O) notation, even a kindergarten would understand.

Big(O) Notation summarized!
Okere chinedu Victor's photo
Okere chinedu Victor

Published on Jun 26, 2021

4 min read

Subscribe to my newsletter and never miss my upcoming articles

Instagram post - 9.png Big(O) is the way in which we compare algorithmic complexities of two programs in a standard manner

Big(O) is an algorithmic complexity metric, which defines the relationship between the number of input and the steps taken by the algorithm to process those inputs.

In summary big(O) measure, the amount of work a program has to do as the input scales. Big(O) in other can be used to define both time and space complexities

Table of Big(O) starting from best case scenarios to worst case scenarios.

Instagram post - 10.png

HOW TO CALCULATE TIME COMPLEXITY USING BIG(O)

CONSTANT COMPLEXITY O(1)

In a constant complexity, the steps taken to complete the execution of a program is always the same regardless of the size of its input.

An execution would be getting an element at a certain position in an array(like getting the alphabet D at the index of 3 in the array).

Instagram post - 12.png

The above takes just one step to complete. The above example, the getAlphabetAt method gets a particular element at a constant position in an array.

No matter how many Alphabet there are in the array the getAlphabetAt method always performs two steps.

  • First, get the element at a certain position.

  • Second, console.logs() the result to the console.

Hence, we can say. The complexity is constant as it doesn’t scale with the input.

Instagram post - 13.png

LINEAR COMPLEXITIES O(N)

In algorithms with linear complexity a single unit increase in the input causes a unit increase in the steps required to complete the program execution.

An example would be calculating power of every element in an array.

This would be linear because as the array grows it would do one unit more of more of that element.

Instagram post - 14.png

The above method getCubicValues() will take 3 steps to complete.

So, for each of them in the array passed as a params to getCubicValues() method, the method finds the cube of each of the item in the array and then logs it to the console.

Functions with linear complexity is represented by straight-line graphs increase in position directions.

Instagram post - 15.png

QUADRATIC COMPLEXITY

In an algorithm with quadratic complexity, the output steps increase quadratically with the increase in the inputs.

Instagram post - 16.png

In the above graphical example, the getProductValue method multiplies each element in that array with other elements.

There are two loops, where the outer loop it rates through each item, and for each of the item in the outer loop, and the inner loop also iterates over each item.

This makes the number of steps to be N*N where N is the number of elements in the array

Instagram post - 17.png

BIG(O) NOTATION FOR SPACE COMPLEXITY

In other to get the space complexity, we calculate the amount of space needed by the algorithms for the input element.

BEST VS WORST CASE SCENERIOS IN COMPLEXITIES

There are two types of complexities

  • Best case scenarios

  • Worst case scenarios

BEST CASE SCENARIOS

This is the complexity of an algorithm in an ideal situation.

An example would be, let’s say we want to search for an item A in an array of N items.

In the best-case scenarios, it would be that we found the item at the fist index in which we can say the complexity would be an O(1).

WORST CASE SCENARIOS

In the worst case, lets assume we find the item at the nth index (last) in this case we can say the complexity would be an O(N) where N is the total number of items in the array.

In summary, and to round it all up, Algorithmic complexities are used as a tool to measure the performance of an algorithm in terms of time taken and space used.

Thank you for sticking with me through this. You Rock.

If you enjoyed pls follow me on Twitter and Instagram , if there are any improvements or code errors do let me know in the comment section below or send a dm.

Thanks once again and bye for now. Much Love❤❤❤.

 
Share this