Algorithms & complexity worksheet with answers

Which notation describes an upper bound on growth?

1. ALittle omega
2. BBig Omega
3. CBig Theta
4. DBig O

What is O(2ⁿ) growth called?

1. ALinear
2. BPolynomial
3. CExponential
4. DLogarithmic

What does binary search require of its input?

1. AThe array must have no more than 1000 elements
2. BThe array length must be a power of two
3. CThe array must be sorted
4. DThe array must contain only positive numbers

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

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

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

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

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

What would follow if someone found a polynomial-time algorithm for one NP-complete problem?

1. AOnly that one problem would move into P
2. BAll exponential-time algorithms would immediately run in linear time
3. CThe halting problem would become decidable
4. DEvery problem in NP could be solved in polynomial time, so P = NP

Why can Dijkstra's algorithm give wrong results when some edge weights are negative?

1. AIt only works on undirected graphs
2. BA vertex is finalised when extracted, but a later negative edge could still give it a shorter path
3. CIt goes into an infinite loop on every negative edge
4. DNegative numbers cannot be stored in a priority queue