Algorithms & complexity worksheet with answers

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

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

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

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

What is the worst-case time complexity of insertion sort?

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

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

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

The lower bound for comparison-based sorting in the worst case is:

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

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

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

Is 2²ⁿ in O(2ⁿ)?

1. AYes, because both are exponential
2. BNo, because 2²ⁿ grows more slowly than 2ⁿ
3. CYes, because constant factors in the exponent are always ignored in Big O
4. DNo, because 2²ⁿ = 4ⁿ and 4ⁿ / 2ⁿ = 2ⁿ grows without bound

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