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. B3 seconds
3. C12 seconds
4. D6 seconds

What is a brute-force algorithm?

1. AOne that guesses an answer at random
2. BOne that tries all possible candidate solutions
3. COne that runs on many processors
4. DOne that always uses recursion

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

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

What does amortised analysis measure?

1. AThe average cost per operation over a worst-case sequence of operations
2. BThe cost of an algorithm on the best input
3. CThe cost of the single most expensive operation anywhere in the sequence
4. DThe expected cost over random inputs

What does the Floyd–Warshall algorithm compute, and how fast?

1. AA topological order in O(V²)
2. BA minimum spanning tree in O(E log V)
3. CShortest paths from one source vertex to all others in O(V + E)
4. DShortest paths between all pairs of vertices in O(V³)

What does it mean that a problem has optimal substructure?

1. AThe problem can be solved in constant time
2. BAn optimal solution can be built from optimal solutions of its subproblems
3. CEvery subproblem has the same size
4. DThe problem has exactly one optimal solution, which every subproblem shares

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

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

Which statement about selecting the k-th smallest element of an unsorted array is correct?

1. AQuickselect runs in expected O(n), and median-of-medians guarantees O(n) worst case
2. BQuickselect runs in O(log n) worst case, because it recurses on only one side of the pivot
3. CSelection is only possible in O(n²)
4. DSelection always needs Ω(n log n) because it requires sorting