Algorithms & complexity worksheet with answers

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

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

A problem is usually called tractable if:

1. AIt can only be solved by trying every possibility
2. BIt can be solved in polynomial time
3. CIt has no solution
4. DIt can be solved in constant time

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

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

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

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

In a sorted array, you look for two elements that sum to a target by moving one pointer from each end inwards. What is the time complexity?

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

A greedy algorithm:

1. AUses only recursion
2. BMakes the locally best choice at each step
3. CTries every possible solution
4. DAlways gives the optimal solution

To show that a new problem X is NP-hard, what must you do?

1. AReduce X to a known NP-hard problem in polynomial time
2. BShow that X can be verified in polynomial time
3. CShow that X has no polynomial algorithm for small inputs
4. DReduce a known NP-hard problem to X in polynomial time

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

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