Algorithms & complexity worksheet with answers

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

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

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

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

What is log₂ 1024?

1. A512
2. B32
3. C10
4. D12

The lower bound for comparison-based sorting in the worst case is:

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

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

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

Quicksort always uses the first element as pivot. On which input does it show its worst-case behaviour?

1. AAn array of length 2
2. BAn array whose elements are all different
3. CAn array that is already sorted
4. DAn array in random order

What is the time complexity of: for i = 1 to n: for (j = i; j ≤ n; j = j + i) do O(1) work?

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

Shortest simple paths can be found in polynomial time. What is known about finding the longest simple path between two vertices in a general graph?

1. AIt can be solved by Dijkstra's algorithm with negated weights
2. BIt is undecidable
3. CIt is NP-hard
4. DIt is always solvable in O(V + E)