Algorithms & complexity worksheet with answers

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

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

What is the running time of counting sort for n integers in the range 0 to k?

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

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)

The lower bound for comparison-based sorting in the worst case is:

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

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

1. AO(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, because Big O is an upper bound and n² grows no faster than n³
2. BNo, because Big O must always state the exact growth rate of the function
3. CNo, because n³ is smaller than n² for large n
4. DYes, but only if n is smaller than 100

Which technique gives an expected O(n log n) running time for quicksort on any input?

1. ASorting the input before running quicksort
2. BChoosing the pivot uniformly at random
3. CAlways choosing the first element
4. DUsing recursion only on the left side

The Held–Karp dynamic programming algorithm solves the travelling salesman problem exactly. What is its running time for n cities?

1. AO(n!)
2. BO(n² 2ⁿ)
3. CO(n³)
4. DO(2^n²)