Algorithms & complexity worksheet with answers

What is the time complexity of linear search in an unsorted array of n elements (worst case)?

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

What does binary search require of its input?

1. AThe array must contain only positive numbers
2. BThe array length must be a power of two
3. CThe array must have no more than 1000 elements
4. DThe array must be sorted

Which of these grows slowest as n becomes large?

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

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

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

Which algorithm finds the shortest paths from one source in a graph with non-negative edge weights?

1. ABellman–Ford is required in all cases
2. BKruskal's algorithm
3. CDepth-first search
4. DDijkstra's algorithm

Breadth-first search on an unweighted graph finds:

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

Insertion sort runs in O(n) on sorted input. Does this contradict the Ω(n log n) lower bound for comparison sorting?

1. AYes, but only for arrays shorter than 100
2. BNo, the lower bound applies to the worst case over all inputs, not to every input
3. CYes, the lower bound is therefore wrong
4. DNo, because insertion sort is not a comparison sort

Using the master theorem, T(n) = 8T(n/2) + O(n²) solves to:

1. AΘ(n³)
2. BΘ(n² log n)
3. CΘ(n²)
4. DΘ(n log n)