What is a Binary Search Algorithm? How does Big O Notation work?
Grokking Algorithms: Chapter 1, Introduction to Algorithms, in 5 Minutes
Have you ever wondered how Facebook finds your profile in milliseconds or how GPS calculates the shortest route? The answer lies in algorithms, a set of instructions for accomplishing a task.
Disclaimer: This blog post condenses the first chapter of “Grokking Algorithms” by Aditya Bhargava, unpacking the fundamentals of algorithms and how they impact our daily lives.
Divide And Conquer With Binary Search Algorithm
Imagine searching a phone book for a specific name. Linear search, checking each name one by one, can be tedious. Binary search offers a much faster alternative for sorted lists. It works by repeatedly dividing the search space in half, discarding half the list based on a comparison with the target element. This process continues until the target is found or eliminated.
For instance, suppose you’re searching for “Karl” in a phone book with 100 names. Binary search would start by checking the name in the middle (around the 50th position). If “Karl” comes alphabetically before the middle name, the search continues in the first half. Conversely, if it comes after, the search moves to the second half. This divide-and-conquer approach significantly reduces the number of comparisons needed, making binary search incredibly efficient.
Understanding Performance of Algorithm Using Big O Notation
While binary search offers a clear advantage over linear search, how can we quantify this difference and predict how algorithms behave with even larger datasets? Big O notation comes to the rescue! It’s a mathematical tool that helps us express the growth rate of an algorithm’s running time about the input size.
Imagine searching a phone book with 10 names versus 10,000 names. A linear search algorithm would take roughly 10 times longer for the larger dataset because it needs to check all the elements one by one. However, binary search only needs to perform a few additional comparisons regardless of the list size, thanks to its divide-and-conquer approach. It will take at most 14 steps for binary search. The base 2 logarithm of 10000 is 13.2877123795.
Big O notation uses terms like O(n) and O(log n) to represent these growth rates. O(n) signifies linear growth, meaning the running time increases proportionally with the input size (n). Conversely, O(log n) signifies logarithmic growth, which increases much slower as the input size grows. This is why binary search, with its logarithmic complexity, remains efficient even for massive datasets.
By understanding Big O notation, you can compare algorithms and predict their performance for different input sizes. This empowers you to choose the most suitable algorithm for a given problem, especially when dealing with large datasets.
Note: The O(log n) always uses 2 as base.
The Traveling Salesman: A Challenge for Efficiency
Not all problems have efficient solutions. The Traveling Salesman Problem (TSP) exemplifies this. Imagine a salesperson with n cities to visit, seeking the shortest route. A naive approach would be to try every possible route, which becomes computationally expensive as n increases. This problem highlights the importance of understanding algorithm complexity and exploring alternative approaches like approximation algorithms for finding near-optimal solutions.
Key Takeaways
Here are some things to take from the first Chapter of this book:
- A binary search is significantly faster than a simple search for sorted lists.
- Big O notation (O(log n)) helps quantify how algorithm efficiency scales with input size, compared to linear notation (O(n)).
- Big O notation represents the worst-case scenario.
- Algorithm speed is measured in terms of growth rate, not seconds.
PS: Comment “Croak” if you liked this blog. Also, learn about “Arrays and Linked Lists ”, from chapter 2 of Grokking Algorithms..
Ready to unlock the world of algorithms? Consider picking up your copy of Grokking Algorithms! This book is one of the top recommendations for professionals wanting to dive deeper into the world of algorithms.
This in Nibesh Khadka. Make sure to show support by liking and sharing this post. Consider subscribing to the email list to get notified regularly about new posts.
This blog was originally published at Script Portal.
