Algorithms & complexity worksheet with answers

Which notation describes an upper bound on growth?

1. ALittle omega
2. BBig O
3. CBig Theta
4. DBig Omega

What are the three steps of a divide-and-conquer algorithm?

1. ADivide, conquer, combine
2. BGuess, check, repeat
3. CRead, compute, write
4. DSort, search, return

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

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

What is the time complexity of the Bellman–Ford algorithm on a graph with V vertices and E edges?

1. AO(V³ × E)
2. BO(V × E)
3. CO(E log V)
4. DO(V + E)

A function runs one loop of n iterations and then, separately, another loop of n iterations. What is its time complexity?

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

Why does dynamic programming give no real speed-up for merge sort?

1. AMerge sort is already O(n)
2. BDynamic programming only works on graph problems, not on arrays
3. CMerge sort has no recursive structure
4. DIts subproblems do not overlap, so there is nothing to reuse

Using the master theorem, T(n) = 8T(n/2) + O(n²) solves to:

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

Strassen's algorithm multiplies matrices using 7 instead of 8 recursive multiplications of half-size blocks. What is its running time?

1. AΘ(n^{log₂ 7}), about n^2.81
2. BΘ(n² log n)
3. CΘ(n²)
4. DΘ(n³)