Algorithms & complexity worksheet with answers

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

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

Which sorting algorithm repeatedly swaps adjacent elements that are in the wrong order?

1. ABubble sort
2. BMerge sort
3. CHeap sort
4. DQuicksort

What does binary search require of its input?

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

What is the time complexity of computing the n-th Fibonacci number with a bottom-up table?

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

What is the time complexity of the Bellman–Ford algorithm on a graph with V vertices and E edges?

1. AO(V + E)
2. BO(E log V)
3. CO(V³ × E)
4. DO(V × E)

Why do many library sorting routines switch to insertion sort for very small subarrays?

1. AInsertion sort has little overhead and is fast on small or nearly sorted inputs
2. BInsertion sort is O(n log n) in the worst case
3. CInsertion sort uses less memory than any other sorting algorithm on large inputs
4. DRecursive algorithms cannot handle arrays below 10 elements

The halting problem shows that:

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

Karatsuba multiplication satisfies T(n) = 3T(n/2) + O(n). What does this solve to?

1. AΘ(n log n)
2. BΘ(n³)
3. CΘ(n^{log₂ 3}), about n^1.585
4. DΘ(n²)