Algorithms & complexity worksheet with answers

What is the worst-case time complexity of insertion sort?

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

What is O(2ⁿ) growth called?

1. ALogarithmic
2. BPolynomial
3. CLinear
4. DExponential

What is log₂ 1024?

1. A512
2. B10
3. C12
4. D32

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

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

How does Prim's algorithm build a minimum spanning tree?

1. AIt sorts all edges by weight and adds each one unless it would form a cycle in the forest
2. BIt runs breadth-first search and keeps the BFS tree
3. CIt removes the most expensive edge until no cycles remain
4. DIt grows one tree from a start vertex, adding the cheapest edge that leaves the tree

Is it correct to say that an O(n²) algorithm is also O(n³)?

1. ANo, because Big O must always state the exact growth rate of the function
2. BYes, because Big O is an upper bound and n² grows no faster than n³
3. CYes, but only if n is smaller than 100
4. DNo, because n³ is smaller than n² for large n

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 is always solvable in O(V + E)
2. BIt is undecidable
3. CIt can be solved by Dijkstra's algorithm with negated weights
4. DIt is NP-hard

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

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