Algorithms & complexity worksheet with answers

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

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

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

1. AQuicksort
2. BBubble sort
3. CInsertion sort
4. DMerge sort

What is the time complexity of binary search on a sorted array?

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

What is the time complexity of the standard dynamic programming algorithm for the longest common subsequence of strings of lengths m and n?

1. AO(mn)
2. BO(m + n)
3. CO(2^m+n)
4. DO(mn log 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²)
4. DO(n² log n)

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

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

Using the master theorem, T(n) = 8T(n/2) + O(n²) solves to:

1. AΘ(n log n)
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n² log n)

The halting problem shows that:

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