Algorithms & complexity worksheet with answers

What is log₂ 1024?

1. A10
2. B32
3. C12
4. D512

Which of these grows slowest as n becomes large?

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

How much extra memory does a standard array-based merge sort use?

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

A recurrence T(n) = 2T(n/2) + O(n) solves to:

1. AO(log n)
2. BO(n log n)
3. CO(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)

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

1. ALinear
2. BLogarithmic
3. CExponential
4. DConstant

Why does binary search not give O(log n) time on a singly linked list?

1. AComparisons on linked list nodes are slower
2. BLinked lists cannot be sorted
3. CBinary search needs at least twice the memory
4. DReaching the middle element takes O(n) steps, since there is no direct index access

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

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