Algorithms & complexity worksheet with answers

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 at the same rate as g, bounded above and below by constant multiples of g
4. Df grows strictly slower than g

What does the worst-case running time of an algorithm describe?

1. AThe time it takes on a slow computer
2. BThe expected time it takes on a random input of size n
3. CThe time it takes on the smallest input
4. DThe maximum time it takes over all inputs of size n

What is an algorithm?

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

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. BThe base only matters for small n
3. CLogarithms with different bases differ only by a constant factor
4. DAll logarithms in computer science have base 10, so it is implied

A greedy algorithm:

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

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

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

What is the difference between an undecidable problem and an intractable one?

1. AAn undecidable problem has no algorithm for all inputs; an intractable one has one, but it is too slow
2. BIntractable problems cannot be solved by any algorithm, while undecidable ones only need exponential time
3. CUndecidable problems are in NP, while intractable problems are in P
4. DBoth mean the problem has no algorithm at all

Strassen's algorithm multiplies matrices using 7 instead of 8 recursive multiplications of half-size blocks. What is its running time?

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