Algorithms & complexity worksheet with answers

Accessing an element by index in an array takes:

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

What is the running time of counting sort for n integers in the range 0 to k?

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

What is O(2ⁿ) growth called?

1. APolynomial
2. BExponential
3. CLogarithmic
4. DLinear

Which sorting algorithm is stable?

1. AQuicksort (typical in-place version)
2. BHeap sort
3. CMerge sort
4. DSelection sort (typical version)

What is the time complexity of multiplying two n × n matrices with the standard triple loop?

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

A function runs one loop of n iterations and then, separately, another loop of n iterations. What is its time complexity?

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

What did the Cook–Levin theorem establish?

1. AThe Boolean satisfiability problem (SAT) is NP-complete
2. BP is not equal to NP
3. CEvery NP problem can be solved in exponential time
4. DThe halting problem is undecidable

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

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