Algorithms & complexity worksheet with answers

Accessing an element by index in an array takes:

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

What does binary search require of its input?

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

What is a brute-force algorithm?

1. AOne that always uses recursion
2. BOne that runs on many processors
3. COne that guesses an answer at random
4. DOne that tries all possible candidate solutions

Which statement about a recursive function without a reachable base case is correct?

1. AIt returns 0 automatically
2. BIt runs in O(1) time
3. CIt keeps calling itself until the call stack overflows
4. DThe compiler always turns it into a loop that ends safely

What is the time complexity of computing the n-th Fibonacci number with a bottom-up table?

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

What does amortised analysis measure?

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

For which knapsack variant does the greedy rule "take items in order of value per weight" always give an optimal answer?

1. AThe fractional knapsack, where items may be split
2. BThe 0/1 knapsack, where items must always be taken whole
3. CNeither variant
4. DBoth variants

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

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