Algorithms & complexity worksheet with answers

What does the average-case running time describe?

1. AThe time on the most common computer
2. BThe expected time over a given distribution of inputs of size n
3. CThe time for an input of average length
4. DThe middle value between the best-case and worst-case running times

What is the time complexity of depth-first search on a graph stored as adjacency lists?

1. AO(V × E)
2. BO(E log V)
3. CO(V + E)
4. DO(V²)

An O(n) algorithm takes 3 seconds for n = 1 million. About how long does it take for n = 2 million?

1. A3 seconds
2. B6 seconds
3. C9 seconds
4. D12 seconds

What does the recurrence T(n) = 2T(n/2) + O(1) solve to?

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

What is the time complexity of the Bellman–Ford algorithm on a graph with V vertices and E edges?

1. AO(V × E)
2. BO(V³ × E)
3. CO(E log V)
4. DO(V + E)

You sort an array of n elements once and then answer k membership queries with binary search. What is the total cost?

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

Insertion sort runs in O(n) on sorted input. Does this contradict the Ω(n log n) lower bound for comparison sorting?

1. AYes, the lower bound is therefore wrong
2. BNo, because insertion sort is not a comparison sort
3. CYes, but only for arrays shorter than 100
4. DNo, the lower bound applies to the worst case over all inputs, not to every input

What did the Cook–Levin theorem establish?

1. AP is not equal to NP
2. BThe Boolean satisfiability problem (SAT) is NP-complete
3. CThe halting problem is undecidable
4. DEvery NP problem can be solved in exponential time