Grokking Algorithms

Run times for
search algorithms

---

11
Big O notation
Running time for 
simple search vs. 
binary search,
with a list of 100 
elements
Algorithm running times grow at different rates
Bob is writing a search algorithm for NASA. His algorithm will kick in 
when a rocket is about to land on the Moon, and it will help calculate 
where to land.
This is an example of how the run time of two algorithms can grow 
at different rates. Bob is trying to decide between simple search and 
binary search. The algorithm needs to be both fast and correct. On one 
hand, binary search is faster. And Bob has only
 10 seconds
to figure out 
where to land—otherwise, the rocket will be off course. On the other 
hand, simple search is easier to write, and there is less chance of bugs 
being introduced. And Bob 
really 
doesn’t want bugs in the code to land 
a rocket! To be extra careful, Bob decides to time both algorithms with 
a list of 100 elements.
Let’s assume it takes 1 millisecond to check one element. With simple 
search, Bob has to check 100 elements, so the search takes 100 ms to 
run. On the other hand, he only has to check 7 elements with binary 
search (log
2
100 is roughly 7), so that search takes 7 ms to run. But 
realistically, the list will have more like a billion elements. If it does, 
how long will simple search take? How long will binary search take? 
Make sure you have an answer for each question before reading on.
Bob runs binary search with 1 billion elements, and it takes 30 ms 
(log
2
1,000,000,000 is roughly 30). “32 ms!” he thinks. “Binary search 
is about 15 times faster than simple search, because simple search took 
100 ms with 100 elements, and binary search took 7 ms. So simple 
search will take 30 × 15 = 450 ms, right? Way under my threshold of
10 seconds.” Bob decides to go with simple search. Is that the right 
choice?

---