Algorithms & complexity worksheet with answers

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

1. ABubble sort
2. BHeap sort
3. CQuicksort
4. DMerge sort

Which of these grows slowest as n becomes large?

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

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

1. A1 second
2. B2 seconds
3. C4 seconds
4. D8 seconds

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

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

A function runs one loop of n iterations and then, separately, another loop of n iterations. What is its time complexity?

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

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(mn log n)
2. BO(2^m+n)
3. CO(mn)
4. DO(m + n)

What is the amortised cost of incrementing a binary counter, given that one increment may flip many bits?

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

Taking both endpoints of every edge in a maximal matching gives a vertex cover. How good is this cover?

1. AAt most twice the size of a minimum vertex cover
2. BOf unknown quality compared to the optimum
3. CAlways a minimum vertex cover
4. DAt most log n times the minimum