Grokking Algorithms

Chapter 4
 
 
I
 
 
Quicksort
EXERCISES
How long would each of these operations take in Big O notation?
4.5
Printing the value of each element in an array. 
4.6 
Doubling the value of each element in an array.
4.7
Doubling the value of just the first element in an array. 
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. 
Recap
• D&C works by breaking a problem down into smaller and smaller 
pieces. If you’re using D&C on a list, the base case is probably an 
empty array or an array with one element.
• If you’re implementing quicksort, choose a random element as the 
pivot. The average runtime of quicksort is O(
n
log 
n
)!
• The constant in Big O notation can matter sometimes. That’s why 
quicksort is faster than merge sort.
• The constant almost never matters for simple search versus binary 
search, because O(log 
n
) is so much faster than O(
n
) when your list 
gets big.

---

73
In this chapter
• You learn about hash tables, one of the most
useful basic data structures. Hash tables have many 
uses; this chapter covers the common use cases.
• You learn about the internals of hash tables:
implementation, collisions, and hash functions. 
This will help you understand how to analyze a 
hash table’s performance.
 
hash tables
5
Suppose you work at a grocery store. When a customer 
buys produce, you have to look up the price in a book. If 
the book is unalphabetized, it can take you a long time to 
look through every single line for 
apple
. You’d be doing 
simple search from chapter 1, where you have to look at 
every line. Do you remember how long that would take? 
O(
n
) time. If the book is alphabetized, you could run 
binary search to find the price of an apple. That would 
only take O(log
 n
) time.

---

74