DEV Community

Cover image for Big(O) Notation summarized!
chinedu | ddevguys
chinedu | ddevguys

Posted on • Updated on • Originally published at ddevguys.com

Big(O) Notation summarized!

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.

  1. First, get the element at a certain position.

  2. 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

  1. Best case scenarios

  2. 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.

Thank You

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❤❤❤.

Top comments (10)

Collapse
 
aminmansuri profile image
hidden_dude

One often missed point in these analyses is that Big-O is based on input SIZE.. so if your algorithm is numeric the SIZE is the number of bits, not the number itself.

Hence, even "linear" versions of the fibonacci algorithm are called "pseudo-polynomial" because in reality their solutions are exponential with respect to the number of bits used.

Collapse
 
chinedu profile image
chinedu | ddevguys

Yes! This wasn't a missed point. The article is like an intro into BigO while taking away the low level complexities.
We all know that just a single article can't be enough to explain the complete concepts of BigO from top to bottom.
Anyways thanks for pointing that out.
I will be writing a more advanced article targeting more experienced folks like yourself.

Cheers😃

Collapse
 
chinedu profile image
chinedu | ddevguys

And once again thank you for pointing this out. Shows you actually read the article!
Thanks alot.❤️

Collapse
 
devmoustafa97 profile image
Moustafa Mahmoud

Great work
Think about making part 2 with examples in js

Collapse
 
alhiane profile image
Alhiane Lahcen

yes pls

Collapse
 
chinedu profile image
chinedu | ddevguys

Great idea! I'll give that a thought!

Collapse
 
chinedu profile image
chinedu | ddevguys

Thank you ❤️

Collapse
 
salarc123 profile image
SalarC123

This was a really well thought out article! I think you should follow this up with articles about big omega and big theta notation as well.

Collapse
 
chinedu profile image
chinedu | ddevguys

Thank you so much. I'll put that I to consideration.

Collapse
 
l1u7 profile image
l1u7

👏 👏 👏