Algorithms & complexity worksheet with answers

What is the base case of a recursive function?

1. AA case that is answered directly without making another recursive call
2. BThe first line of the function
3. CThe call that uses the most memory
4. DThe case with the largest input, which is handled before any recursive calls

Which notation describes an upper bound on growth?

1. ABig Omega
2. BBig Theta
3. CLittle omega
4. DBig O

A problem is usually called tractable if:

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

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

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

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 log n)
2. BO(log n)
3. CO(n)
4. DO(n²)

What is the amortised time complexity of appending to a dynamic array that doubles its capacity when full?

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

Why is the average lookup in a hash table O(1) but the worst case O(n)?

1. AArrays have O(n) access
2. BHash functions are slow
3. CMany keys may collide into the same bucket
4. DKeys must be sorted first

Which algorithm finds a minimum spanning tree by repeatedly adding the cheapest edge that does not form a cycle?

1. AKruskal's algorithm
2. BFloyd–Warshall
3. CDijkstra's algorithm
4. DPrim's algorithm starting from one node