Chapter 4: Quicksort

Question 1

Write out the code for the earlier sum function.

Answer 1

Question 2

Write a recursive function to count the number of items in a list.

Answer 2

Question 3

Find the maximum number in a list.

Answer 3

Question 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 4

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.

Question 5

Printing the value of each element in an array. What’s the big O

Answer 5

O(n)

Question 6

Doubling the value of each element in an array. Big O?

Answer 6

O(n)

Question 7

Doubling the value of just the first element in an array. Big O?

Answer 7

O(1)

Question 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 8

O(n^2)