Algorithms & complexity worksheet with answers

A problem is usually called tractable if:

1. AIt can be solved in polynomial time
2. BIt can only be solved by trying every possibility
3. CIt has no solution
4. DIt can be solved in constant time

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

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

An algorithm with two nested loops, each running n times, typically has which complexity?

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

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

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

In the activity selection problem, which greedy rule always gives a maximum number of non-overlapping activities?

1. APick the activity with the fewest overlaps first, then repeat with the compatible ones
2. BPick the activity that finishes earliest, then repeat with the compatible ones
3. CPick the activity that starts earliest
4. DPick the shortest activity first

In a sorted array, you look for two elements that sum to a target by moving one pointer from each end inwards. What is the time complexity?

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

What is the time complexity of building a binary heap from n unsorted elements with the bottom-up method?

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

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

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