Algorithms & complexity worksheet with answers

What is the best-case time complexity of insertion sort, on an already sorted array?

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

Which notation describes an upper bound on growth?

1. ABig Omega
2. BBig O
3. CLittle omega
4. DBig Theta

An algorithm's running time is O(n). What is this growth called?

1. ALogarithmic
2. BLinear
3. CConstant
4. DQuadratic

Dynamic programming is useful when a problem has:

1. AA single loop
2. BNo subproblems at all, so it can be solved in one step
3. COnly random inputs
4. DOverlapping subproblems and optimal substructure

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 log n + k log n)
2. BO(k n log n)
3. CO(nk)
4. DO(n + k)

What does amortised analysis measure?

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

Is 2²ⁿ in O(2ⁿ)?

1. ANo, because 2²ⁿ = 4ⁿ and 4ⁿ / 2ⁿ = 2ⁿ grows without bound
2. BYes, because both are exponential
3. CNo, because 2²ⁿ grows more slowly than 2ⁿ
4. DYes, because constant factors in the exponent are always ignored in Big O

Which bound is correct for log(n!)?

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