Algorithms & complexity worksheet with answers

Which of these running times is polynomial?

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

Which complexity class grows fastest for large n?

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

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

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

A greedy algorithm:

1. AAlways gives the optimal solution
2. BUses only recursion
3. CMakes the locally best choice at each step
4. DTries every possible solution

Which sorting algorithm is stable?

1. AQuicksort (typical in-place version)
2. BSelection sort (typical version)
3. CHeap sort
4. DMerge sort

A recurrence T(n) = 2T(n/2) + O(n) solves to:

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

The halting problem shows that:

1. ASome programs run faster on faster computers, so halting depends on hardware
2. BLoops should be avoided
3. CNo algorithm can decide for every program and input whether it halts
4. DEvery program eventually halts

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 counts the cycles with depth-first search
3. CIt runs Dijkstra's algorithm twice and compares the two distance results
4. DIt checks whether any edge has a negative weight