Algorithms & complexity worksheet with answers

Which of these grows slowest as n becomes large?

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

Which notation describes a lower bound on growth?

1. AΘ (Big Theta)
2. Bo (little o)
3. CΩ (Big Omega)
4. DO (Big O)

How much extra memory does a standard array-based merge sort use?

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

In the activity selection problem, which greedy rule always gives a maximum number of non-overlapping activities?

1. APick the shortest activity first
2. BPick the activity with the fewest overlaps first, then repeat with the compatible ones
3. CPick the activity that finishes earliest, then repeat with the compatible ones
4. DPick the activity that starts earliest

What is the time complexity of computing the n-th Fibonacci number with a bottom-up table?

1. AO(2ⁿ)
2. BO(n)
3. CO(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. BLogarithms with different bases differ only by a constant factor
3. CThe base only matters for small n
4. DAll logarithms in computer science have base 10, so it is implied

Why can Dijkstra's algorithm give wrong results when some edge weights are negative?

1. AA vertex is finalised when extracted, but a later negative edge could still give it a shorter path
2. BNegative numbers cannot be stored in a priority queue
3. CIt only works on undirected graphs
4. DIt goes into an infinite loop on every negative edge

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

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