Algorithms & complexity worksheet with answers

What does the average-case running time describe?

1. AThe expected time over a given distribution of inputs of size n
2. BThe time for an input of average length
3. CThe middle value between the best-case and worst-case running times
4. DThe time on the most common computer

What is a brute-force algorithm?

1. AOne that always uses recursion
2. BOne that tries all possible candidate solutions
3. COne that runs on many processors
4. DOne that guesses an answer at random

Which notation describes an upper bound on growth?

1. ABig Theta
2. BLittle omega
3. CBig O
4. DBig Omega

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

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

Which statement about a recursive function without a reachable base case is correct?

1. AIt keeps calling itself until the call stack overflows
2. BIt runs in O(1) time
3. CThe compiler always turns it into a loop that ends safely
4. DIt returns 0 automatically

Which sorting algorithm is stable?

1. AHeap sort
2. BMerge sort
3. CQuicksort (typical in-place version)
4. DSelection sort (typical version)

Which statement about little-o notation is correct?

1. An² = o(n)
2. Bn = o(n²), but n is not o(n)
3. C2n = o(n), because 2n grows slowly
4. Dn = o(n), since every function is little-o of itself

Why is the average lookup in a hash table O(1) but the worst case O(n)?

1. AMany keys may collide into the same bucket
2. BKeys must be sorted first
3. CArrays have O(n) access
4. DHash functions are slow