Algorithms & complexity worksheet with answers

What is the Big O of 3n² + 5n + 2?

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

An algorithm with two nested loops, each running n times, typically has which complexity?

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

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

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

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

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

What does it mean that a problem has optimal substructure?

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

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

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

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

1. AFloyd–Warshall
2. BDijkstra's algorithm
3. CKruskal's algorithm
4. DPrim's algorithm starting from one node

Why can Dijkstra's algorithm give wrong results when some edge weights are negative?

1. AIt goes into an infinite loop on every negative edge
2. BIt only works on undirected graphs
3. CNegative numbers cannot be stored in a priority queue
4. DA vertex is finalised when extracted, but a later negative edge could still give it a shorter path