Algorithms & complexity worksheet with answers

What is the base case of a recursive function?

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

What is the time complexity of finding the largest value in an unsorted array of n numbers?

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

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

1. A2 seconds
2. B4 seconds
3. C8 seconds
4. D1 second

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

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

What is the worst-case time complexity of quicksort?

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

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

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

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. BAlways a minimum vertex cover
3. CAt most log n times the minimum
4. DOf unknown quality compared to the optimum

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

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