Algorithms & complexity worksheet with answers

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

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

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

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

What does the worst-case running time of an algorithm describe?

1. AThe expected time it takes on a random input of size n
2. BThe maximum time it takes over all inputs of size n
3. CThe time it takes on the smallest input
4. DThe time it takes on a slow computer

What does amortised analysis measure?

1. AThe expected cost over random inputs
2. BThe cost of an algorithm on the best input
3. CThe cost of the single most expensive operation anywhere in the sequence
4. DThe average cost per operation over a worst-case sequence of operations

A function runs one loop of n iterations and then, separately, another loop of n iterations. What is its time complexity?

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

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

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

Using the master theorem, T(n) = 8T(n/2) + O(n²) solves to:

1. AΘ(n log n)
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n² log n)

Which statement about P and NP is correct?

1. ANP means "not polynomial"
2. BEvery problem in P is also in NP
3. CNP problems cannot be verified quickly
4. DIt has been proven that P ≠ NP