Algorithms & complexity worksheet with answers

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)

What is log₂ 1024?

1. A32
2. B512
3. C12
4. D10

An O(n²) algorithm takes 1 second for n = 1000. About how long does it take for n = 2000?

1. A4 seconds
2. B2 seconds
3. C8 seconds
4. D1 second

What does amortised analysis measure?

1. AThe average cost per operation over a worst-case sequence of operations
2. BThe expected cost over random inputs
3. CThe cost of the single most expensive operation anywhere in the sequence
4. DThe cost of an algorithm on the best input

Quicksort always uses the first element as pivot. On which input does it show its worst-case behaviour?

1. AAn array that is already sorted
2. BAn array in random order
3. CAn array of length 2
4. DAn array whose elements are all different

What is the time complexity of the standard dynamic programming algorithm for the longest common subsequence of strings of lengths m and n?

1. AO(2^m+n)
2. BO(mn log n)
3. CO(m + n)
4. DO(mn)

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

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

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

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