Algorithms & complexity worksheet with answers

What is the time complexity of finding the largest value in an unsorted array of n numbers?

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

How does selection sort work?

1. AIt splits the array in halves and merges them
2. BIt inserts each element into a growing sorted part by shifting
3. CIt repeatedly finds the minimum of the unsorted part and swaps it to the front
4. DIt repeatedly swaps neighbouring elements that are in the wrong order

What is an algorithm?

1. AA finite sequence of well-defined steps that solves a problem
2. BAny computer program that has a graphical interface
3. CA data structure that stores numbers
4. DA programming language designed for writing mathematical formulas

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

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

Why does dynamic programming give no real speed-up for merge sort?

1. ADynamic programming only works on graph problems, not on arrays
2. BIts subproblems do not overlap, so there is nothing to reuse
3. CMerge sort has no recursive structure
4. DMerge sort is already O(n)

What is the time complexity of computing the n-th Fibonacci number with a bottom-up table?

1. AO(log n)
2. BO(2ⁿ)
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 is in NP, and a known NP-complete problem reduces to X in polynomial time
3. CX has no polynomial algorithm, and X is decidable
4. DX reduces to a problem in P, and X is in NP

Which statement about little-o notation is correct?

1. An = o(n²), but n is not o(n)
2. Bn² = o(n)
3. Cn = o(n), since every function is little-o of itself
4. D2n = o(n), because 2n grows slowly