Algorithms & complexity worksheet with answers

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

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

What is the Big O of 3n² + 5n + 2?

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

Which notation describes a lower bound on growth?

1. AΩ (Big Omega)
2. Bo (little o)
3. CO (Big O)
4. DΘ (Big Theta)

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

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

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

Why is the base of a logarithm usually left out in Big O, as in O(log n)?

1. ALogarithms are always rounded to integers
2. BAll logarithms in computer science have base 10, so it is implied
3. CLogarithms with different bases differ only by a constant factor
4. DThe base only matters for small n

What did the Cook–Levin theorem establish?

1. AEvery NP problem can be solved in exponential time
2. BP is not equal to NP
3. CThe halting problem is undecidable
4. DThe Boolean satisfiability problem (SAT) is NP-complete

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

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