Algorithms & complexity worksheet with answers

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

1. AConstant
2. BLogarithmic
3. CLinear
4. DQuadratic

What are the three steps of a divide-and-conquer algorithm?

1. ARead, compute, write
2. BDivide, conquer, combine
3. CSort, search, return
4. DGuess, check, repeat

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. 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

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

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

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

What is the worst-case time complexity of quicksort?

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

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

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

What are the time and space costs of computing the n-th Fibonacci number with a loop that keeps only the last two values?

1. AO(n) time and O(n) space
2. BO(2ⁿ) time and O(1) space
3. CO(log n) time and O(n) space
4. DO(n) time and O(1) space