Algorithms & complexity worksheet with answers

How does selection sort work?

1. AIt inserts each element into a growing sorted part by shifting
2. BIt repeatedly swaps neighbouring elements that are in the wrong order
3. CIt splits the array in halves and merges them
4. DIt repeatedly finds the minimum of the unsorted part and swaps it to the front

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

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

What is memoisation?

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

What is the time complexity of: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

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

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

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 4 coins; the optimum is 3
3. CGreedy uses 3 coins; the optimum is 2
4. DGreedy uses 3 coins; the optimum is 3

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

1. APrim's algorithm starting from one node
2. BDijkstra's algorithm
3. CFloyd–Warshall
4. DKruskal's algorithm

Is 2²ⁿ in O(2ⁿ)?

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