Algorithms & complexity worksheet with answers

Which notation describes a lower bound on growth?

1. Ao (little o)
2. BO (Big O)
3. CΘ (Big Theta)
4. DΩ (Big Omega)

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

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

Which notation describes an upper bound on growth?

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

Quicksort always uses the first element as pivot. On which input does it show its worst-case behaviour?

1. AAn array in random order
2. BAn array whose elements are all different
3. CAn array that is already sorted
4. DAn array of length 2

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

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

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

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

The halting problem shows that:

1. ANo algorithm can decide for every program and input whether it halts
2. BEvery program eventually halts
3. CSome programs run faster on faster computers, so halting depends on hardware
4. DLoops should be avoided

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

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