Algorithms & complexity worksheet with answers

An algorithm's running time is O(n). What is this growth called?

1. ALogarithmic
2. BLinear
3. CConstant
4. DQuadratic

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

1. ABubble sort
2. BMerge sort
3. CQuicksort
4. DHeap sort

What is the base case of a recursive function?

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

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

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

Is it correct to say that an O(n²) algorithm is also O(n³)?

1. AYes, because Big O is an upper bound and n² grows no faster than n³
2. BNo, because Big O must always state the exact growth rate of the function
3. CNo, because n³ is smaller than n² for large n
4. DYes, but only if n is smaller than 100

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 whose elements are all different
3. CAn array in random order
4. DAn array of length 2

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

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

To show that a new problem X is NP-hard, what must you do?

1. AReduce a known NP-hard problem to X in polynomial time
2. BShow that X has no polynomial algorithm for small inputs
3. CReduce X to a known NP-hard problem in polynomial time
4. DShow that X can be verified in polynomial time