Algorithms & complexity worksheet with answers

Which of these running times is polynomial?

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

What is the base case of a recursive function?

1. AA case that is answered directly without making another recursive call
2. BThe call that uses the most memory
3. CThe first line of the function
4. DThe case with the largest input, which is handled before any recursive calls

What does f(n) = Θ(g(n)) mean?

1. Af grows strictly faster than g
2. Bf grows strictly slower than g
3. Cf grows at the same rate as g, bounded above and below by constant multiples of g
4. Df is always smaller than g for every n, so g bounds it from above but never from below

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

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

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

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

Which statement about a recursive function without a reachable base case is correct?

1. AThe compiler always turns it into a loop that ends safely
2. BIt keeps calling itself until the call stack overflows
3. CIt returns 0 automatically
4. DIt runs in O(1) time

Topological sorting is possible only for:

1. AUndirected graphs
2. BGraphs with negative weights
3. CDirected acyclic graphs
4. DComplete graphs

How does the Bellman–Ford algorithm detect a negative-weight cycle reachable from the source?

1. AAfter V − 1 rounds, it checks whether any edge can still be relaxed
2. BIt runs Dijkstra's algorithm twice and compares the two distance results
3. CIt counts the cycles with depth-first search
4. DIt checks whether any edge has a negative weight