Algorithms & complexity worksheet with answers

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

1. AQuicksort
2. BMerge sort
3. CHeap sort
4. DBubble sort

What is the worst-case time complexity of insertion sort?

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

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

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

What is the time complexity of multiplying two n × n matrices with the standard triple loop?

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

Why is the base of a logarithm usually left out in Big O, as in O(log n)?

1. ALogarithms are always rounded to integers
2. BAll logarithms in computer science have base 10, so it is implied
3. CThe base only matters for small n
4. DLogarithms with different bases differ only by a constant factor

What does the recurrence T(n) = 2T(n/2) + O(1) solve to?

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

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. BBoth mean the problem has no algorithm at all
3. CUndecidable problems are in NP, while intractable problems are in P
4. DAn undecidable problem has no algorithm for all inputs; an intractable one has one, but it is too slow

Karatsuba multiplication satisfies T(n) = 3T(n/2) + O(n). What does this solve to?

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