Algorithms & complexity worksheet with answers

Which of these running times is polynomial?

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

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

1. A8 seconds
2. B1 second
3. C2 seconds
4. D4 seconds

Which notation describes a lower bound on growth?

1. Ao (little o)
2. BΘ (Big Theta)
3. CO (Big O)
4. DΩ (Big Omega)

How does Prim's algorithm build a minimum spanning tree?

1. AIt removes the most expensive edge until no cycles remain
2. BIt runs breadth-first search and keeps the BFS tree
3. CIt grows one tree from a start vertex, adding the cheapest edge that leaves the tree
4. DIt sorts all edges by weight and adds each one unless it would form a cycle in the forest

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(mn)
2. BO(m + n)
3. CO(2^m+n)
4. DO(mn log n)

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

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

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

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

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²)
3. CO(n log n)
4. DO(n √n)