Algorithms & complexity worksheet with answers

What is the time complexity of finding the largest value in an unsorted array of n numbers?

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

What is a brute-force algorithm?

1. AOne that tries all possible candidate solutions
2. BOne that guesses an answer at random
3. COne that runs on many processors
4. DOne that always uses recursion

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

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

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

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

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

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

What is the time complexity of: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

How does the Bellman–Ford algorithm detect a negative-weight cycle reachable from the source?

1. AIt checks whether any edge has a negative weight
2. BIt runs Dijkstra's algorithm twice and compares the two distance results
3. CAfter V − 1 rounds, it checks whether any edge can still be relaxed
4. DIt counts the cycles with depth-first search

Why is the average lookup in a hash table O(1) but the worst case O(n)?

1. AMany keys may collide into the same bucket
2. BHash functions are slow
3. CArrays have O(n) access
4. DKeys must be sorted first