Algorithms & complexity worksheet with answers

Which notation describes an upper bound on growth?

1. ABig Theta
2. BLittle omega
3. CBig Omega
4. DBig O

An algorithm's running time is O(n). What is this growth called?

1. AConstant
2. BQuadratic
3. CLogarithmic
4. DLinear

Which notation describes a lower bound on growth?

1. AO (Big O)
2. BΩ (Big Omega)
3. Co (little o)
4. DΘ (Big Theta)

Quicksort always uses the first element as pivot. On which input does it show its worst-case behaviour?

1. AAn array of length 2
2. BAn array whose elements are all different
3. CAn array that is already sorted
4. DAn array in random order

What is the worst-case time complexity of quicksort?

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

Breadth-first search on an unweighted graph finds:

1. AA topological order in all graphs
2. BShortest paths in number of edges from the start node
3. CShortest paths in graphs that contain negative edge weights
4. DThe minimum spanning tree

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 n)
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n^{log₂ 7}), about n^2.81

What did the Cook–Levin theorem establish?

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