Introduction to Algorithms and Big O Notation
What is an Algorithm?
If you ever wondered how a GPS device calculates the shortest route to your destination or how youtube recommendations work, then this blog is for you!
The answer to the above questions is simple — They use algorithms. GPS devices use graph algorithms and YouTube uses deep learning and ranking algorithms. So, what exactly is an algorithm?
An Algorithm is a set of instructions for accomplishing a task.
Algorithms are solutions to specific problems. They are not programming languages but they are implemented using languages like python, java, etc.
Let’s start with a simple Algorithm
Suppose I told you to look for a word (say, “Lucid”) in the dictionary, you might start from the beginning and flip through the pages till you find the word or you might start at the middle, flip the pages and find the word.
Both approaches are algorithms and the second one is better than the first because you get to the word a lot faster.
Similarly, When you enter your credentials to log into a website (say, Twitter) the servers search for your username in a database. If they were using the first approach, i.e, starting all the way from the beginning, then it would take a long time and they will eventually lose their customers.
So, In this case, a search algorithm called Binary Search is used.
Binary Search
Binary search is a search algorithm that finds the position of a target (like, username) in a sorted list. It does this by reducing the search area into halves.
To understand it better: Let’s play a guessing game
I have thought of a number which is between 1 and 100 and I want you to guess it.
Suppose you guess 1, I tell you “Nope, it’s too low.”
now, you guess 2, I tell you “Nope, it’s too low.”
now, you guess 3, I tell you “Nope, it’s too low.”
now, you guess 4, I tell you “Nope, it’s too low.”
If this continued and the number I thought of was “99”, then it would take you a long time to get there.
Instead, what a binary search algorithm does is that it reduces the search area.
We start the game again:
This time you guess 50, I tell you “Nope, it’s too low.”
Now, you only have to guess from 51 to 100, that’s quite a reduction!
This time you guess 75, I tell you “Nope, it’s too low.”
Now, you only have to guess numbers between 76 to 100.
Again, the search area is reduced.
This continues and you get to the number “99” in 6 steps.
Time Taken by Binary Search
For 100 numbers, the first approach or simple search would take 100 steps whereas binary search would only take 6 steps.
For a list of 8 numbers, the simple search would take 8 steps.
For a list of 8 numbers, the binary search would take 3 steps.
For a list of 16 numbers, the simple search would take 16 steps.
For a list of 16 numbers, the binary search would take 4 steps.
For n elements of a list, a simple search would take n steps. This is called Linear time because if you were to plot it, it would be a linear graph.
For n elements of a list, the binary search would take log n (base 2) steps. This is called Logarithmic time. If you were to plot it, it would be a logarithmic graph.
So, we compared both the search algorithms and learnt that simple search was a lot slower than binary search. The number of steps taken by the algorithms is represented using the Big O notation.
Big O Notation
Big O notation tells you the number of operations the algorithm will take to get to the answer.
For Simple Search, the time complexity or no. of steps is O(n). It is pronounced as “Big o (because the o is big) of n”. It means that for any input of n elements, in the worst-case scenario, the algorithm will take n steps.
For example, in a list of 100 elements, if I thought of “1” then you could easily guess the answer in 1 step, but if I chose 100, it’d take 100 steps. Big O notation represents the worst-case scenario.
For Binary Search, the time complexity or no. of steps is O(log n).
Why Big O?
We use Big O notation to describe how long an algorithm takes to run aka Time Complexity and how much memory is used by the algorithm aka Space complexity.
It is a way of comparing algorithms in terms of speed of execution and memory usage.
This brings us to the end of this story. Stay tuned for more!
© Shreya Sinha 2021.
Written by Shreya Sinha, Thank you for reading.
Author’s note: Most websites use data structures like B-Trees or binary search trees to store your credentials. These data structures are based on the binary search algorithm.
