Algorithms & complexity worksheet with answers

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

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

A loop starts with i = 1 and doubles i each iteration until i > n. How many iterations does it run?

1. AAbout n²
2. BAbout log₂ n
3. CAbout n / 2
4. DAbout n

An O(n) algorithm takes 3 seconds for n = 1 million. About how long does it take for n = 2 million?

1. A12 seconds
2. B3 seconds
3. C9 seconds
4. D6 seconds

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

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

What is the time complexity of multiplying two n × n matrices with the standard triple loop?

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

How much stack space does a simple recursive factorial function fact(n) = n × fact(n − 1) use?

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

What is the time complexity of building a binary heap from n unsorted elements with the bottom-up method?

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

Why does binary search not give O(log n) time on a singly linked list?

1. AComparisons on linked list nodes are slower
2. BBinary search needs at least twice the memory
3. CReaching the middle element takes O(n) steps, since there is no direct index access
4. DLinked lists cannot be sorted