Algorithms & complexity worksheet with answers

Which sorting algorithm chooses a pivot and partitions the array into smaller and larger elements?

1. ABubble sort
2. BInsertion sort
3. CQuicksort
4. DMerge sort

What does the average-case running time describe?

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

Which of these running times is polynomial?

1. AO(nⁿ)
2. BO(2ⁿ)
3. CO(n!)
4. DO(n³)

How much stack space does a simple recursive factorial function fact(n) = n × fact(n − 1) use?

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

What is the worst-case time complexity of quicksort?

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

What does amortised analysis measure?

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

Which technique gives an expected O(n log n) running time for quicksort on any input?

1. AAlways choosing the first element
2. BSorting the input before running quicksort
3. CUsing recursion only on the left side
4. DChoosing the pivot uniformly at random

What is the difference between an undecidable problem and an intractable one?

1. AIntractable problems cannot be solved by any algorithm, while undecidable ones only need exponential time
2. BUndecidable problems are in NP, while intractable problems are in P
3. CAn undecidable problem has no algorithm for all inputs; an intractable one has one, but it is too slow
4. DBoth mean the problem has no algorithm at all