Algorithms & complexity worksheet with answers

What is the time complexity of binary search on a sorted array?

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

Space complexity measures:

1. AThe disk space of the program file once it is compiled
2. BThe physical size of the computer
3. CThe number of lines of code
4. DThe amount of memory an algorithm needs as input grows

Which of these grows slowest as n becomes large?

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

With coins of 1, 3 and 4 and an amount of 6, how many coins does the greedy "largest coin first" method use, compared to the optimum?

1. AGreedy uses 4 coins; the optimum is 3
2. BGreedy uses 2 coins; the optimum is 2
3. CGreedy uses 3 coins; the optimum is 2
4. DGreedy uses 3 coins; the optimum is 3

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

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

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

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

What are the time and space costs of computing the n-th Fibonacci number with a loop that keeps only the last two values?

1. AO(log n) time and O(n) space
2. BO(n) time and O(n) space
3. CO(2ⁿ) time and O(1) space
4. DO(n) time and O(1) space

What would follow if someone found a polynomial-time algorithm for one NP-complete problem?

1. AThe halting problem would become decidable
2. BAll exponential-time algorithms would immediately run in linear time
3. CEvery problem in NP could be solved in polynomial time, so P = NP
4. DOnly that one problem would move into P