Hello there !
Welcome and stay with me as I explain Big O Notation to you in the simplest words ever!
"Total time needed for an algorithm to run," is the simplest definition of Big O Notation, but why does it matter to you as a developer?
To answer that, below is a simple search Algorithm that finds any given item in an array; if the given item is not in the array, our algorithm returns null.
Simple Search Algorithm.
Fig 1.0 (For-loop search algorithm )
The above is a simple JavaScript For-loop that iterates over each item in the array, checks if the current iteration equals our input ('item' ), and if the item is not in the array, it returns "null."
Below (Fig 2.0 ) is a while loop that does the same as the above For-loop.
Binary Search Algorithm.
Fig 2.0 (while loop search algorithm )
Although, the above functions do precisely the same thing. But what happens when the number of items in our array increases exponentially?
How efficient will both our algorithms still be ?
A step-by-step break-down of the Binary Search Algorithm:
- We compare 'item' with the middle index of the array.
- if 'item' matches the mid index, we return the mid element.
- else if 'item' is greater than the middle element, length of the array is reassigned to the middle ( element - 1 ).
- else if 'item' is lesser than the middle element, beginning of the array is reassigned to the middle ( element + 1 ).
With this method we eliminate half of the array in the first comparison.
For better understanding,
If the length of the array increases to 1millon.
With the first function (Fig 1.0), we will perform 1 million iterations (worst case) to find our item. However, we will perform at most 10 iterations (worst case) with the second function.
The Big O notation of our functions.
Simple search algorithm (Fig 1.0) - O(n) // Bad guy
Binary search algorithm (Fig 2.0) - O(log n) // Good guy.
Stay with me on this blog while I explain Algorithms and Data Structures as succinctly as possible.
Link to Code and remember to give it a star.
https://github.com/Olatisunkanmi/Data-Structures-and-Algorithms-/tree/main/5%20Algorithms/Binary%20Search
Top comments (13)
Nice write up
Interesting. I learnt something
This was super helpful ππ½
Nice one βΊοΈ
Thanks for the article.
One thing I would like to point out is that to be able to apply the binary search, we must have a sorted array.
Yes.
This is an amazing write up, nice one!
Thank you π
Amazing write-up π
Thank you
Good read..πͺ
shouldn't simple search be O(n)? O(1) is constant time
Thank you so much, totally!