Algorithms & complexity worksheet with answers

Which of these grows slowest as n becomes large?

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

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

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

Which complexity class grows fastest for large n?

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

Breadth-first search on an unweighted graph finds:

1. AThe minimum spanning tree
2. BA topological order in all graphs
3. CShortest paths in graphs that contain negative edge weights
4. DShortest paths in number of edges from the start node

The lower bound for comparison-based sorting in the worst case is:

1. AΩ(log n)
2. BΩ(n log n)
3. CΩ(n)
4. DΩ(n²)

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

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

The halting problem shows that:

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

Shortest simple paths can be found in polynomial time. What is known about finding the longest simple path between two vertices in a general graph?

1. AIt can be solved by Dijkstra's algorithm with negated weights
2. BIt is undecidable
3. CIt is always solvable in O(V + E)
4. DIt is NP-hard