Algorithms & complexity worksheet with answers

Which sorting algorithm chooses a pivot and partitions the array into smaller and larger elements?

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

What is the time complexity of depth-first search on a graph stored as adjacency lists?

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

What is the worst-case time complexity of insertion sort?

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

Is it correct to say that an O(n²) algorithm is also O(n³)?

1. AYes, but only if n is smaller than 100
2. BYes, because Big O is an upper bound and n² grows no faster than n³
3. CNo, because n³ is smaller than n² for large n
4. DNo, because Big O must always state the exact growth rate of the function

What is the time complexity of the standard dynamic programming algorithm for the longest common subsequence of strings of lengths m and n?

1. AO(2^m+n)
2. BO(mn log n)
3. CO(mn)
4. DO(m + n)

You sort an array of n elements once and then answer k membership queries with binary search. What is the total cost?

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

The halting problem shows that:

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

Strassen's algorithm multiplies matrices using 7 instead of 8 recursive multiplications of half-size blocks. What is its running time?

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