Algorithms & complexity worksheet with answers

Which of these running times is polynomial?

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

How much extra memory does a standard array-based merge sort use?

1. AO(log n)
2. BO(n²)
3. CO(1)
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 at the same rate as g, bounded above and below by constant multiples of g
3. Cf grows strictly faster than g
4. Df grows strictly slower than g

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

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

Why is the base of a logarithm usually left out in Big O, as in O(log n)?

1. ALogarithms with different bases differ only by a constant factor
2. BThe base only matters for small n
3. CAll logarithms in computer science have base 10, so it is implied
4. DLogarithms are always rounded to integers

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

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

Topological sorting is possible only for:

1. AComplete graphs
2. BUndirected graphs
3. CDirected acyclic graphs
4. DGraphs with negative weights

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

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