Algorithms & complexity worksheet with answers

What are the three steps of a divide-and-conquer algorithm?

1. ADivide, conquer, combine
2. BGuess, check, repeat
3. CSort, search, return
4. DRead, compute, write

Which notation describes an upper bound on growth?

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

Which sorting algorithm repeatedly swaps adjacent elements that are in the wrong order?

1. AHeap sort
2. BMerge sort
3. CQuicksort
4. DBubble sort

What does amortised analysis measure?

1. AThe average cost per operation over a worst-case sequence of operations
2. BThe cost of the single most expensive operation anywhere in the sequence
3. CThe cost of an algorithm on the best input
4. DThe expected cost over random inputs

How many levels does the recursion of merge sort have for an array of n elements?

1. AAbout n
2. BAbout log₂ n
3. CAbout n / 2
4. DAbout √n

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

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

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. BThe halting problem would become decidable
3. CAll exponential-time algorithms would immediately run in linear time
4. DEvery problem in NP could be solved in polynomial time, so P = NP

The halting problem shows that:

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