Algorithms & complexity worksheet with answers

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

1. ARead, compute, write
2. BSort, search, return
3. CGuess, check, repeat
4. DDivide, conquer, combine

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

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

What is the running time of counting sort for n integers in the range 0 to k?

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

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

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

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ⁿ)

Dynamic programming is useful when a problem has:

1. AOverlapping subproblems and optimal substructure
2. BNo subproblems at all, so it can be solved in one step
3. COnly random inputs
4. DA single loop

Which bound is correct for log(n!)?

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

The Held–Karp dynamic programming algorithm solves the travelling salesman problem exactly. What is its running time for n cities?

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