Algorithms & complexity worksheet with answers

Which of these running times is polynomial?

1. AO(n³)
2. BO(nⁿ)
3. CO(2ⁿ)
4. DO(n!)

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

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

What is an algorithm?

1. AA programming language designed for writing mathematical formulas
2. BA finite sequence of well-defined steps that solves a problem
3. CAny computer program that has a graphical interface
4. DA data structure that stores numbers

Why does dynamic programming give no real speed-up for merge sort?

1. ADynamic programming only works on graph problems, not on arrays
2. BMerge sort is already O(n)
3. CMerge sort has no recursive structure
4. DIts subproblems do not overlap, so there is nothing to reuse

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

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

A greedy algorithm:

1. AMakes the locally best choice at each step
2. BAlways gives the optimal solution
3. CTries every possible solution
4. DUses only recursion

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

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

Which technique gives an expected O(n log n) running time for quicksort on any input?

1. AUsing recursion only on the left side
2. BChoosing the pivot uniformly at random
3. CSorting the input before running quicksort
4. DAlways choosing the first element