Algorithms & complexity worksheet with answers

What is the time complexity of linear search in an unsorted array of n elements (worst case)?

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

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

1. ABubble sort
2. BMerge sort
3. CHeap sort
4. DQuicksort

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

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

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 cost of an algorithm on the best input
4. DThe average cost per operation over a worst-case sequence of operations

A recurrence T(n) = 2T(n/2) + O(n) solves to:

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

About how many comparisons does binary search need in the worst case on a sorted array of 1,000,000 elements?

1. AAbout 20
2. BAbout 500,000
3. CAbout 100
4. DAbout 1,000

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

Strassen's algorithm multiplies matrices using 7 instead of 8 recursive multiplications of half-size blocks. What is its running time?

1. AΘ(n²)
2. BΘ(n² log n)
3. CΘ(n³)
4. DΘ(n^{log₂ 7}), about n^2.81