Algorithms & complexity worksheet with answers

What is the time complexity of finding the largest value in an unsorted array of n numbers?

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

Which complexity class grows fastest for large n?

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

Which of these grows slowest as n becomes large?

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

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

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

Which sorting algorithm is stable?

1. AMerge sort
2. BQuicksort (typical in-place version)
3. CHeap sort
4. DSelection sort (typical version)

What does amortised analysis measure?

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

The halting problem shows that:

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

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

1. AChoosing the pivot uniformly at random
2. BAlways choosing the first element
3. CUsing recursion only on the left side
4. DSorting the input before running quicksort