Algorithms & complexity worksheet with answers

What is O(2ⁿ) growth called?

1. ALogarithmic
2. BPolynomial
3. CExponential
4. DLinear

Which notation describes an upper bound on growth?

1. ABig O
2. BBig Omega
3. CBig Theta
4. DLittle omega

What is the time complexity of linear search in an unsorted array of n elements (worst case)?

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

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

1. AO(n²)
2. BO(log n)
3. CO(1)
4. DO(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 3 coins; the optimum is 3
2. BGreedy uses 2 coins; the optimum is 2
3. CGreedy uses 3 coins; the optimum is 2
4. DGreedy uses 4 coins; the optimum is 3

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

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

To show that a new problem X is NP-hard, what must you do?

1. AReduce X to a known NP-hard problem in polynomial time
2. BReduce a known NP-hard problem to X in polynomial time
3. CShow that X can be verified in polynomial time
4. DShow that X has no polynomial algorithm for small inputs

Which technique gives an expected O(n log n) running time for quicksort on any input?

1. ASorting the input before running quicksort
2. BUsing recursion only on the left side
3. CAlways choosing the first element
4. DChoosing the pivot uniformly at random