Algorithms & complexity worksheet with answers

A problem is usually called tractable if:

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

How does selection sort work?

1. AIt splits the array in halves and merges them
2. BIt repeatedly finds the minimum of the unsorted part and swaps it to the front
3. CIt repeatedly swaps neighbouring elements that are in the wrong order
4. DIt inserts each element into a growing sorted part by shifting

What is an algorithm?

1. AAny computer program that has a graphical interface
2. BA finite sequence of well-defined steps that solves a problem
3. CA programming language designed for writing mathematical formulas
4. DA data structure that stores numbers

How much stack space does a simple recursive factorial function fact(n) = n × fact(n − 1) use?

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

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

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

Which statement about a recursive function without a reachable base case is correct?

1. AIt runs in O(1) time
2. BThe compiler always turns it into a loop that ends safely
3. CIt returns 0 automatically
4. DIt keeps calling itself until the call stack overflows

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

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

Which bound is correct for log(n!)?

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