Algorithms & complexity worksheet with answers

What is log₂ 1024?

1. A10
2. B512
3. C12
4. D32

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

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

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

1. AGuess, check, repeat
2. BRead, compute, write
3. CSort, search, return
4. DDivide, conquer, combine

In a sorted array, you look for two elements that sum to a target by moving one pointer from each end inwards. What is the time complexity?

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

What is the running time of LSD radix sort on n integers with d digits in base k?

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

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

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

The halting problem shows that:

1. ALoops should be avoided
2. BNo algorithm can decide for every program and input whether it halts
3. CSome programs run faster on faster computers, so halting depends on hardware
4. DEvery program eventually halts

Why does any comparison-based search in a sorted array need Ω(log n) comparisons in the worst case?

1. AComparisons take logarithmic time each
2. BBinary search is the only possible algorithm, and it needs log₂ n comparisons
3. CEvery element must be compared at least once
4. DA decision tree with n possible outcomes must have depth at least log₂ n