Algorithms & complexity worksheet with answers

A problem is usually called tractable if:

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

Accessing an element by index in an array takes:

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

What is the time complexity of finding the largest value in an unsorted array of n numbers?

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

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. BNo, because Big O must always state the exact growth rate of the function
3. CNo, because n³ is smaller than n² for large n
4. DYes, because Big O is an upper bound and n² grows no faster than n³

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

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

The time complexity of naive recursive Fibonacci (fib(n) = fib(n−1) + fib(n−2)) is:

1. AExponential
2. BLinear
3. CLogarithmic
4. DConstant

What is the running time of Dijkstra's algorithm with a binary heap on a graph with V vertices and E edges?

1. AO(V + E)
2. BO(V³)
3. CO((V + E) log V)
4. DO(V × E)

Which statement about selecting the k-th smallest element of an unsorted array is correct?

1. AQuickselect runs in O(log n) worst case, because it recurses on only one side of the pivot
2. BQuickselect runs in expected O(n), and median-of-medians guarantees O(n) worst case
3. CSelection always needs Ω(n log n) because it requires sorting
4. DSelection is only possible in O(n²)