Algorithms & complexity worksheet with answers

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

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

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

1. ASort, search, return
2. BRead, compute, write
3. CDivide, conquer, combine
4. DGuess, check, repeat

Accessing an element by index in an array takes:

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

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. BMerge sort is already O(n)
3. CDynamic programming only works on graph problems, not on arrays
4. DMerge sort has no recursive structure

What does the Floyd–Warshall algorithm compute, and how fast?

1. AA minimum spanning tree in O(E log V)
2. BShortest paths between all pairs of vertices in O(V³)
3. CShortest paths from one source vertex to all others in O(V + E)
4. DA topological order in O(V²)

How much stack space does a simple recursive factorial function fact(n) = n × fact(n − 1) use?

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

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

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

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

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