Algorithms & complexity worksheet with answers

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

1. AMerge sort
2. BBubble sort
3. CInsertion sort
4. DQuicksort

Which complexity class grows fastest for large n?

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

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. CStoring the results of function calls so repeated calls are answered from memory
4. DWriting comments next to each line of code

How much stack space does a simple recursive factorial function fact(n) = n × fact(n − 1) use?

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

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

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

What is the time complexity of the Bellman–Ford algorithm on a graph with V vertices and E edges?

1. AO(V + E)
2. BO(V × E)
3. CO(V³ × E)
4. DO(E log V)

How is the travelling salesman problem classified?

1. AThe decision version is in P but the optimisation version is NP-complete
2. BIt is undecidable
3. CThe decision version is NP-complete and the optimisation version is NP-hard
4. DIt is in P because Dijkstra's algorithm solves it by visiting every city once

Why is the average lookup in a hash table O(1) but the worst case O(n)?

1. AMany keys may collide into the same bucket
2. BHash functions are slow
3. CKeys must be sorted first
4. DArrays have O(n) access