Algorithms & complexity worksheet with answers

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

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

What does the worst-case running time of an algorithm describe?

1. AThe expected time it takes on a random input of size n
2. BThe time it takes on a slow computer
3. CThe time it takes on the smallest input
4. DThe maximum time it takes over all inputs of size n

What is the time complexity of binary search on a sorted array?

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

A greedy algorithm:

1. AUses only recursion
2. BAlways gives the optimal solution
3. CMakes the locally best choice at each step
4. DTries every possible solution

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 2
2. BGreedy uses 3 coins; the optimum is 3
3. CGreedy uses 2 coins; the optimum is 2
4. DGreedy uses 4 coins; the optimum is 3

What is the time complexity of computing the n-th Fibonacci number with a bottom-up table?

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

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

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

Insertion sort runs in O(n) on sorted input. Does this contradict the Ω(n log n) lower bound for comparison sorting?

1. ANo, the lower bound applies to the worst case over all inputs, not to every input
2. BYes, but only for arrays shorter than 100
3. CYes, the lower bound is therefore wrong
4. DNo, because insertion sort is not a comparison sort