Algorithms & complexity worksheet with answers

What is the best-case time complexity of insertion sort, on an already sorted array?

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

An O(n²) algorithm takes 1 second for n = 1000. About how long does it take for n = 2000?

1. A4 seconds
2. B2 seconds
3. C8 seconds
4. D1 second

What is the base case of a recursive function?

1. AThe call that uses the most memory
2. BThe first line of the function
3. CA case that is answered directly without making another recursive call
4. DThe case with the largest input, which is handled before any recursive calls

Which sorting algorithm is stable?

1. AMerge sort
2. BQuicksort (typical in-place version)
3. CHeap sort
4. DSelection sort (typical version)

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

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

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

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

Which definition of the class NP is correct?

1. AProblems that cannot be solved in polynomial time
2. BDecision problems whose yes-answers can be verified in polynomial time given a certificate
3. CProblems that are not polynomial
4. DProblems that no algorithm can solve

How do n! and 2ⁿ compare for large n?

1. An! is O(n²)
2. B2ⁿ grows faster than n!
3. CThey grow at the same rate
4. Dn! grows faster than 2ⁿ