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