4 Big-O notation: A framework for measuring algorithm efficiency
In this chapter
- How we can objectively compare different algorithms?
- What’s the big-O notation, and how can we use it to understand data structures?
- What’s the difference between worst-case, average, and amortized analysis?
- A formal comparative analysis of binary search and linear search.
In chapter 3, we discussed how binary search seems faster than linear search, but we didn’t have the tools to explain why. In this chapter, we introduce an analysis technique that will change the way you work - and that's an understatement. After reading this chapter, you'll be able to distinguish between the high-level analysis of the performance of algorithms and data structures and the more concrete analysis of your code’s running time. This will help you choose the right data structure and avoid bottlenecks before you dive into implementing code. With a little upfront effort, this will save you a lot of time and pain.
How do we choose the best option?
In the last chapter, we saw two methods for searching a sorted array: linear search and binary search. I told you that binary search is faster than linear search, and you could see an example where binary search needed only a few comparisons, while linear search had to scan almost the whole array instead.
