Grokking Algorithms

return list[0] if list[0] > sub_max else sub_max
4.4
Remember binary search from chapter 1? It’s a divide-and-
conquer algorithm, too. Can you come up with the base case and 
recursive case for binary search?
 Answer: 
The base case for binary search is an array with one item. 
If the item you’re looking for matches the item in the array, you 
found it! Otherwise, it isn’t in the array.
In the recursive case for binary search, you split the array in half, 
throw away one half, and call binary search on the other half.
How long would each of these operations take in Big O notation?
4.5
Printing the value of each element in an array. 
Answer:
O(
n
)
4.6
Doubling the value of each element in an array. 
Answer:
O(
n
)
4.7
Doubling the value of just the first element in an array. 
 Answer:
O(1)
answers to exercises

---

227
4.8
Creating a multiplication table with all the elements in the array. 
So if your array is [2, 3, 7, 8, 10], you first multiply every element 
by 2, then multiply every element by 3, then by 7, and so on. 
 Answer:
O(
n
2
)
CHAPTER 5
Which of these hash functions are consistent?
5.1
f(x) = 1
Returns “1” for all input
Answer: 
Consistent
5.2
f(x) = rand()
Returns a random number every time
Answer: 
Not consistent
5.3
f(x) = next_empty_slot()
Returns the index of the next
empty slot in the hash table
Answer: 
Not consistent
5.4
f(x) = len(x)