Algorithms & complexity worksheet with answers

Which notation describes an upper bound on growth?

1. ABig Theta
2. BLittle omega
3. CBig Omega
4. DBig O

What is the best-case time complexity of insertion sort, on an already sorted array?

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

What is recursion?

1. AA loop that never ends
2. BA type of data structure
3. CA function that calls itself on smaller inputs
4. DA sorting method

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

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

A greedy algorithm:

1. AMakes the locally best choice at each step
2. BTries every possible solution
3. CUses only recursion
4. DAlways gives the optimal solution

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

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

Insertion sort runs in O(n) on sorted input. Does this contradict the Ω(n log n) lower bound for comparison sorting?

1. ANo, the lower bound applies to the worst case over all inputs, not to every input
2. BYes, the lower bound is therefore wrong
3. CNo, because insertion sort is not a comparison sort
4. DYes, but only for arrays shorter than 100

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. BIt goes into an infinite loop on every negative edge
3. CNegative numbers cannot be stored in a priority queue
4. DIt only works on undirected graphs