Algorithms & complexity worksheet with answers

What does binary search require of its input?

1. AThe array length must be a power of two
2. BThe array must contain only positive numbers
3. CThe array must have no more than 1000 elements
4. DThe array must be sorted

What is the time complexity of linear search in an unsorted array of n elements (worst case)?

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

What is the time complexity of binary search on a sorted array?

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

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

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

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

1. ALogarithmic
2. BConstant
3. CExponential
4. DLinear

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

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

What are the time and space costs of computing the n-th Fibonacci number with a loop that keeps only the last two values?

1. AO(n) time and O(n) space
2. BO(log n) time and O(n) space
3. CO(2ⁿ) time and O(1) space
4. DO(n) time and O(1) space

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

1. ASelection is only possible in O(n²)
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. DQuickselect runs in O(log n) worst case, because it recurses on only one side of the pivot