Algorithms & complexity worksheet with answers

Which sorting algorithm repeatedly swaps adjacent elements that are in the wrong order?

1. AQuicksort
2. BHeap sort
3. CMerge sort
4. DBubble sort

What does f(n) = Θ(g(n)) mean?

1. Af grows strictly slower than g
2. Bf grows strictly faster than g
3. Cf grows at the same rate as g, bounded above and below by constant multiples of g
4. Df is always smaller than g for every n, so g bounds it from above but never from below

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

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

You sort an array of n elements once and then answer k membership queries with binary search. What is the total cost?

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

What is the time complexity of: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Karatsuba multiplication satisfies T(n) = 3T(n/2) + O(n). What does this solve to?

1. AΘ(n^{log₂ 3}), about n^1.585
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n log n)

How does the Bellman–Ford algorithm detect a negative-weight cycle reachable from the source?

1. AAfter V − 1 rounds, it checks whether any edge can still be relaxed
2. BIt counts the cycles with depth-first search
3. CIt runs Dijkstra's algorithm twice and compares the two distance results
4. DIt checks whether any edge has a negative weight