Algorithms & complexity worksheet with answers

Which of these running times is polynomial?

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

What is memoisation?

1. AFreeing memory after a function returns
2. BStoring the results of function calls so repeated calls are answered from memory
3. CWriting comments next to each line of code
4. DConverting recursion into an equivalent loop automatically so no call stack is needed

Space complexity measures:

1. AThe number of lines of code
2. BThe disk space of the program file once it is compiled
3. CThe physical size of the computer
4. DThe amount of memory an algorithm needs as input grows

Which sorting algorithm is stable?

1. AMerge sort
2. BHeap sort
3. CQuicksort (typical in-place version)
4. DSelection sort (typical version)

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

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

What is the time complexity of the standard dynamic programming algorithm for the longest common subsequence of strings of lengths m and n?

1. AO(2^m+n)
2. BO(m + n)
3. CO(mn log n)
4. DO(mn)

The 0/1 knapsack problem solved with dynamic programming takes O(nW) time. Why is this called pseudo-polynomial?

1. AW is a number, so the time is exponential in the number of bits used to write W
2. BBecause the algorithm is randomised and its running time varies with each input
3. CBecause n is always small
4. DBecause it only works for W = 0

Is 2²ⁿ in O(2ⁿ)?

1. ANo, because 2²ⁿ grows more slowly than 2ⁿ
2. BYes, because both are exponential
3. CNo, because 2²ⁿ = 4ⁿ and 4ⁿ / 2ⁿ = 2ⁿ grows without bound
4. DYes, because constant factors in the exponent are always ignored in Big O