Algorithms & complexity worksheet with answers

Which complexity class grows fastest for large n?

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

Which of these grows slowest as n becomes large?

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

An algorithm's running time is O(n). What is this growth called?

1. AConstant
2. BQuadratic
3. CLogarithmic
4. DLinear

What does amortised analysis measure?

1. AThe cost of an algorithm on the best input
2. BThe average cost per operation over a worst-case sequence of operations
3. CThe expected cost over random inputs
4. DThe cost of the single most expensive operation anywhere in the sequence

What is the time complexity of: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Quicksort always uses the first element as pivot. On which input does it show its worst-case behaviour?

1. AAn array in random order
2. BAn array that is already sorted
3. CAn array of length 2
4. DAn array whose elements are all different

Which two things must be shown to prove that a decision problem X is NP-complete?

1. AX is in NP, and a known NP-complete problem reduces to X in polynomial time
2. BX reduces to a problem in P, and X is in NP
3. CX has no polynomial algorithm, and X is decidable
4. DX is in P, and X reduces to SAT

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

1. AΘ(n)
2. BΘ(n log² n)
3. CΘ(n²)
4. DΘ(n log n)