Algorithms & complexity worksheet with answers

What does the average-case running time describe?

1. AThe expected time over a given distribution of inputs of size n
2. BThe time on the most common computer
3. CThe middle value between the best-case and worst-case running times
4. DThe time for an input of average length

What does f(n) = Θ(g(n)) mean?

1. Af grows strictly slower than g
2. Bf grows at the same rate as g, bounded above and below by constant multiples of g
3. Cf grows strictly faster than g
4. Df is always smaller than g for every n, so g bounds it from above but never from below

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
4. DAbout n / 2

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 is the time complexity of the Bellman–Ford algorithm on a graph with V vertices and E edges?

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

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

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

Why is the average lookup in a hash table O(1) but the worst case O(n)?

1. AHash functions are slow
2. BKeys must be sorted first
3. CMany keys may collide into the same bucket
4. DArrays have O(n) access

What is the time complexity of: for i = 1 to n: for (j = i; j ≤ n; j = j + i) do O(1) work?

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