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 th
e irst 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 irst 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. he average runtime of quicksort is O(
n
log 
n
)!
• he constant in Big O notation can matter sometimes. hat’s why 
quicksort is faster than merge sort.
• he 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 t
o ind the price of an apple. hat would 
only take O(log
n
) time.

---

74