Algorithms & complexity worksheet with answers

What does the worst-case running time of an algorithm describe?

1. AThe time it takes on a slow computer
2. BThe maximum time it takes over all inputs of size n
3. CThe expected time it takes on a random input of size n
4. DThe time it takes on the smallest input

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

1. AGuess, check, repeat
2. BSort, search, return
3. CDivide, conquer, combine
4. DRead, compute, write

Which sorting algorithm chooses a pivot and partitions the array into smaller and larger elements?

1. AMerge sort
2. BQuicksort
3. CBubble sort
4. DInsertion sort

Quicksort always uses the first element as pivot. On which input does it show its worst-case behaviour?

1. AAn array that is already sorted
2. BAn array of length 2
3. CAn array whose elements are all different
4. DAn array in random order

In a sorted array, you look for two elements that sum to a target by moving one pointer from each end inwards. What is the time complexity?

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

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

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

The Held–Karp dynamic programming algorithm solves the travelling salesman problem exactly. What is its running time for n cities?

1. AO(2^n²)
2. BO(n² 2ⁿ)
3. CO(n!)
4. DO(n³)

Which definition of the class P is correct?

1. AProblems whose solutions can be checked but never found in polynomial time
2. BDecision problems solvable by a deterministic algorithm in polynomial time
3. CProblems that need exponential time on every computer
4. DProblems that can be solved in parallel