Algorithms & complexity worksheet with answers

An algorithm with two nested loops, each running n times, typically has which complexity?

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

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

1. ALinear
2. BConstant
3. CQuadratic
4. DLogarithmic

Which design strategy does merge sort use?

1. AGreedy choice
2. BBrute force
3. CDivide and conquer
4. DDynamic programming

Why do many library sorting routines switch to insertion sort for very small subarrays?

1. ARecursive algorithms cannot handle arrays below 10 elements
2. BInsertion sort is O(n log n) in the worst case
3. CInsertion sort uses less memory than any other sorting algorithm on large inputs
4. DInsertion sort has little overhead and is fast on small or nearly sorted inputs

What is the worst-case time complexity of quicksort?

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

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

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

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

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

The Held–Karp dynamic programming algorithm solves the travelling salesman problem exactly. What is its running time for n cities?

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