Algorithms & complexity worksheet with answers

Space complexity measures:

1. AThe amount of memory an algorithm needs as input grows
2. BThe number of lines of code
3. CThe disk space of the program file once it is compiled
4. DThe physical size of the computer

What does f(n) = Θ(g(n)) mean?

1. Af grows strictly faster than g
2. Bf is always smaller than g for every n, so g bounds it from above but never from below
3. Cf grows strictly slower than g
4. Df grows at the same rate as g, bounded above and below by constant multiples of g

What are the three steps of a divide-and-conquer algorithm?

1. ADivide, conquer, combine
2. BGuess, check, repeat
3. CRead, compute, write
4. DSort, search, return

What is the time complexity of: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

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

1. ADynamic programming only works on graph problems, not on arrays
2. BIts subproblems do not overlap, so there is nothing to reuse
3. CMerge sort has no recursive structure
4. DMerge sort is already O(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. BAll logarithms in computer science have base 10, so it is implied
3. CLogarithms with different bases differ only by a constant factor
4. DThe base only matters for small n

Karatsuba multiplication satisfies T(n) = 3T(n/2) + O(n). What does this solve to?

1. AΘ(n^{log₂ 3}), about n^1.585
2. BΘ(n³)
3. CΘ(n log n)
4. DΘ(n²)

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, the lower bound is therefore wrong
3. CNo, the lower bound applies to the worst case over all inputs, not to every input
4. DYes, but only for arrays shorter than 100