Algorithms & complexity worksheet with answers

What are the three steps of a divide-and-conquer algorithm?

1. ADivide, conquer, combine
2. BSort, search, return
3. CRead, compute, write
4. DGuess, check, repeat

What is log₂ 1024?

1. A10
2. B32
3. C12
4. D512

Which of these grows slowest as n becomes large?

1. AO(n²)
2. BO(log n)
3. CO(n)
4. DO(n log n)

Why do many library sorting routines switch to insertion sort for very small subarrays?

1. ARecursive algorithms cannot handle arrays below 10 elements
2. BInsertion sort is O(n log n) in the worst case
3. CInsertion sort has little overhead and is fast on small or nearly sorted inputs
4. DInsertion sort uses less memory than any other sorting algorithm on large inputs

Which statement about a recursive function without a reachable base case is correct?

1. AThe compiler always turns it into a loop that ends safely
2. BIt keeps calling itself until the call stack overflows
3. CIt runs in O(1) time
4. DIt returns 0 automatically

What does the recurrence T(n) = 2T(n − 1) + O(1) solve to?

1. AO(n log n)
2. BO(2ⁿ)
3. CO(n²)
4. DO(n)

What does the recurrence T(n) = 2T(n/2) + n log n solve to?

1. AΘ(n²)
2. BΘ(n log n)
3. CΘ(n log² n)
4. DΘ(n)

What is the time complexity of: for i = 1 to n: for (j = i; j ≤ n; j = j + i) do O(1) work?

1. AO(n)
2. BO(n √n)
3. CO(n log n)
4. DO(n²)