Algorithms & complexity worksheet with answers

What is the worst-case time complexity of insertion sort?

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

What is the base case of a recursive function?

1. AThe first line of the function
2. BThe call that uses the most memory
3. CThe case with the largest input, which is handled before any recursive calls
4. DA case that is answered directly without making another recursive call

Space complexity measures:

1. AThe disk space of the program file once it is compiled
2. BThe physical size of the computer
3. CThe number of lines of code
4. DThe amount of memory an algorithm needs as input grows

What does the recurrence T(n) = 2T(n − 1) + O(1) solve to?

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

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

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

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

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

Using the master theorem, T(n) = 8T(n/2) + O(n²) solves to:

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

Insertion sort runs in O(n) on sorted input. Does this contradict the Ω(n log n) lower bound for comparison sorting?

1. AYes, the lower bound is therefore wrong
2. BNo, because insertion sort is not a comparison sort
3. CYes, but only for arrays shorter than 100
4. DNo, the lower bound applies to the worst case over all inputs, not to every input