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)
4. DO(n log n)

What is a brute-force algorithm?

1. AOne that always uses recursion
2. BOne that runs on many processors
3. COne that tries all possible candidate solutions
4. DOne that guesses an answer at random

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

Which statement about a recursive function without a reachable base case is correct?

1. AIt keeps calling itself until the call stack overflows
2. BIt returns 0 automatically
3. CIt runs in O(1) time
4. DThe compiler always turns it into a loop that ends safely

Why does dynamic programming give no real speed-up for merge sort?

1. AIts subproblems do not overlap, so there is nothing to reuse
2. BDynamic programming only works on graph problems, not on arrays
3. CMerge sort has no recursive structure
4. DMerge sort is already O(n)

Which algorithm finds the shortest paths from one source in a graph with non-negative edge weights?

1. ADijkstra's algorithm
2. BKruskal's algorithm
3. CDepth-first search
4. DBellman–Ford is required in all cases

Is 2²ⁿ in O(2ⁿ)?

1. ANo, because 2²ⁿ = 4ⁿ and 4ⁿ / 2ⁿ = 2ⁿ grows without bound
2. BNo, because 2²ⁿ grows more slowly than 2ⁿ
3. CYes, because both are exponential
4. DYes, because constant factors in the exponent are always ignored in Big O

How do n! and 2ⁿ compare for large n?

1. An! is O(n²)
2. B2ⁿ grows faster than n!
3. Cn! grows faster than 2ⁿ
4. DThey grow at the same rate