Algorithms & complexity worksheet with answers

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

1. A6 seconds
2. B9 seconds
3. C3 seconds
4. D12 seconds

What is a brute-force algorithm?

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

Which of these grows slowest as n becomes large?

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

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

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

In a sorted array, you look for two elements that sum to a target by moving one pointer from each end inwards. What is the time complexity?

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

With coins of 1, 3 and 4 and an amount of 6, how many coins does the greedy "largest coin first" method use, compared to the optimum?

1. AGreedy uses 2 coins; the optimum is 2
2. BGreedy uses 3 coins; the optimum is 2
3. CGreedy uses 3 coins; the optimum is 3
4. DGreedy uses 4 coins; the optimum is 3

Which definition of the class P is correct?

1. AProblems that can be solved in parallel
2. BProblems whose solutions can be checked but never found in polynomial time
3. CDecision problems solvable by a deterministic algorithm in polynomial time
4. DProblems that need exponential time on every computer

What is the running time of Dijkstra's algorithm with a binary heap on a graph with V vertices and E edges?

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