Algorithms & complexity worksheet with answers

What does it mean if an operation runs in O(1) time?

1. AIt can only be run once
2. BIts running time does not grow with the input size
3. CIt always takes exactly one second
4. DIt processes exactly one element per second of running time

What is memoisation?

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

A problem is usually called tractable if:

1. AIt can be solved in polynomial time
2. BIt can only be solved by trying every possibility
3. CIt has no solution
4. DIt can be solved in constant time

What is the time complexity of multiplying two n × n matrices with the standard triple loop?

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

Which sorting algorithm is stable?

1. ASelection sort (typical version)
2. BHeap sort
3. CQuicksort (typical in-place version)
4. DMerge sort

A function runs one loop of n iterations and then, separately, another loop of n iterations. What is its time complexity?

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

Which statement about P and NP is correct?

1. ANP means "not polynomial"
2. BNP problems cannot be verified quickly
3. CIt has been proven that P ≠ NP
4. DEvery problem in P is also in NP

Strassen's algorithm multiplies matrices using 7 instead of 8 recursive multiplications of half-size blocks. What is its running time?

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