Algorithms & complexity worksheet with answers

What is recursion?

1. AA type of data structure
2. BA sorting method
3. CA loop that never ends
4. DA function that calls itself on smaller inputs

Space complexity measures:

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

What is memoisation?

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

You sort an array of n elements once and then answer k membership queries with binary search. What is the total cost?

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

Why does dynamic programming give no real speed-up for merge sort?

1. AIts subproblems do not overlap, so there is nothing to reuse
2. BDynamic programming only works on graph problems, not on arrays
3. CMerge sort has no recursive structure
4. DMerge sort is already O(n)

The time complexity of naive recursive Fibonacci (fib(n) = fib(n−1) + fib(n−2)) is:

1. AConstant
2. BLinear
3. CLogarithmic
4. DExponential

Which algorithm finds a minimum spanning tree by repeatedly adding the cheapest edge that does not form a cycle?

1. ADijkstra's algorithm
2. BFloyd–Warshall
3. CPrim's algorithm starting from one node
4. DKruskal's algorithm

Is 2²ⁿ in O(2ⁿ)?

1. AYes, because both are exponential
2. BNo, because 2²ⁿ = 4ⁿ and 4ⁿ / 2ⁿ = 2ⁿ grows without bound
3. CYes, because constant factors in the exponent are always ignored in Big O
4. DNo, because 2²ⁿ grows more slowly than 2ⁿ