Grokking Algorithms

Appendix. Answers to Exercises

Chapter 1

1.1

Suppose you have a sorted list of 128 names, and you’re searching through it using binary search. What’s the maximum number of steps it would take?

Answer:

7.

1.2

Suppose you double the size of the list. What’s the maximum number of steps now?

Answer:

8.

1.3

You have a name, and you want to find the person’s phone number in the phone book.

Answer:

O(log n).

1.4

You have a phone number, and you want to find the person’s name in the phone book. (Hint: You’ll have to search through the whole book!)

Answer:

O(n).

1.5

You want to read the numbers of every person in the phone book. ...