Here are the running times of some operations we might perform on the phone book, from best to worst:
-
O(1)
(best case) Given the page that a business's name is on and the business name, find the phone number. -
O(1)
(average case) Given the page that a person's name is on and their name, find the phone number. -
O(log n)
Given a person's name, find the phone number by picking a random point about halfway through the part of the book you haven't searched yet, then checking to see whether the person's name is at that point. Then repeat the process about halfway through the part of the book where the person's name lies. (This is a binary search for a person's name).