The Big 'O' Notation

The Big 'O' Notation

Arpan Pandey
·Dec 28, 2021·

2 min read

Subscribe to my newsletter and never miss my upcoming articles

Play this article

Table of contents

  • The meaning
  • O(n)
  • O(log n)
  • Wrap Up..

Have you ever heard people talk about the big 'O' of an algorithm? Well, I certainly have done. Let's distil it down in this short post.

The meaning

The Big 'O' notation is just a way to estimate the running time or space complexity of a problem. It is used by Computer Scientists to estimate the running time and cost of an algorithm. It may be in terms of time, space or something like that. The Big 'O' specifically takes the worst case scenario that the particular algorithm can face.

BreakDown of O(n).png

O(n)

Let's say that we are searching a word in a dictionary. We may arbitrarily search each page until we find the word. If the no. of pages in the book is say n pages long. It would take us n steps to find a solution in the worst case. Or if you are searching 2 pages at a time then it would be n/2 steps. This algorithm by the way is called Linear Search. This is represented as the O(n). For simplicity, we trim of the /2 because we only focus on the main variable. The actual thing may be say n - 1, n-5, n/2, 2n etc. and would still be counted as O(n). This is as David here, put it, a wave of the hand.

O(n)and O(n/2) Graph.png

O(log n)

What if you searched through the same dictionary. But this time, start from the middle and start splitting the book. Like open at somewhere near M then see if the letter you need is on the left or right. Again open in the middle of that half of the book and repeat. This would be represented as O(log n), or logarithmic complexity. O(n)and O(log n) Graph.png

Wrap Up..

So, this was all. Thank you for reading. See ya later!

Did you find this article valuable?

Support Arpan Pandey by becoming a sponsor. Any amount is appreciated!

See recent sponsors Learn more about Hashnode Sponsors
 
Share this