Algorithms & complexity worksheet with answers

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

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

An algorithm with two nested loops, each running n times, typically has which complexity?

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

What are the three steps of a divide-and-conquer algorithm?

1. ASort, search, return
2. BGuess, check, repeat
3. CDivide, conquer, combine
4. DRead, compute, write

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

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

Why is the base of a logarithm usually left out in Big O, as in O(log n)?

1. ALogarithms with different bases differ only by a constant factor
2. BLogarithms are always rounded to integers
3. CAll logarithms in computer science have base 10, so it is implied
4. DThe base only matters for small n

The lower bound for comparison-based sorting in the worst case is:

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

Shortest simple paths can be found in polynomial time. What is known about finding the longest simple path between two vertices in a general graph?

1. AIt can be solved by Dijkstra's algorithm with negated weights
2. BIt is undecidable
3. CIt is always solvable in O(V + E)
4. DIt is NP-hard

Which statement about selecting the k-th smallest element of an unsorted array is correct?

1. ASelection is only possible in O(n²)
2. BQuickselect runs in expected O(n), and median-of-medians guarantees O(n) worst case
3. CSelection always needs Ω(n log n) because it requires sorting
4. DQuickselect runs in O(log n) worst case, because it recurses on only one side of the pivot