Algorithms & complexity worksheet with answers

What is the time complexity of linear search in an unsorted array of n elements (worst case)?

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

What is a brute-force algorithm?

1. AOne that runs on many processors
2. BOne that always uses recursion
3. COne that tries all possible candidate solutions
4. DOne that guesses an answer at random

Which notation describes an upper bound on growth?

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

A recurrence T(n) = 2T(n/2) + O(n) solves to:

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

Is it correct to say that an O(n²) algorithm is also O(n³)?

1. AYes, but only if n is smaller than 100
2. BNo, because n³ is smaller than n² for large n
3. CYes, because Big O is an upper bound and n² grows no faster than n³
4. DNo, because Big O must always state the exact growth rate of the function

What is the amortised time complexity of appending to a dynamic array that doubles its capacity when full?

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

Which two things must be shown to prove that a decision problem X is NP-complete?

1. AX is in P, and X reduces to SAT
2. BX reduces to a problem in P, and X is in NP
3. CX is in NP, and a known NP-complete problem reduces to X in polynomial time
4. DX has no polynomial algorithm, and X is decidable

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

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