Algorithms & complexity worksheet with answers

An O(n) algorithm takes 3 seconds for n = 1 million. About how long does it take for n = 2 million?

1. A9 seconds
2. B6 seconds
3. C12 seconds
4. D3 seconds

What is the time complexity of binary search on a sorted array?

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

Which design strategy does merge sort use?

1. ADivide and conquer
2. BDynamic programming
3. CGreedy choice
4. DBrute force

With coins of 1, 3 and 4 and an amount of 6, how many coins does the greedy "largest coin first" method use, compared to the optimum?

1. AGreedy uses 2 coins; the optimum is 2
2. BGreedy uses 3 coins; the optimum is 2
3. CGreedy uses 4 coins; the optimum is 3
4. DGreedy uses 3 coins; the optimum is 3

Is it correct to say that an O(n²) algorithm is also O(n³)?

1. ANo, because n³ is smaller than n² for large n
2. BNo, because Big O must always state the exact growth rate of the function
3. CYes, but only if n is smaller than 100
4. DYes, because Big O is an upper bound and n² grows no faster than n³

In the activity selection problem, which greedy rule always gives a maximum number of non-overlapping activities?

1. APick the shortest activity first
2. BPick the activity with the fewest overlaps first, then repeat with the compatible ones
3. CPick the activity that starts earliest
4. DPick the activity that finishes earliest, then repeat with the compatible ones

Karatsuba multiplication satisfies T(n) = 3T(n/2) + O(n). What does this solve to?

1. AΘ(n log n)
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n^{log₂ 3}), about n^1.585

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 the algorithm is randomised and its running time varies with each input
4. DBecause n is always small