Algorithms & complexity worksheet with answers

How much extra memory does a standard array-based merge sort use?

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

What is O(2ⁿ) growth called?

1. ALinear
2. BPolynomial
3. CLogarithmic
4. DExponential

What is the worst-case time complexity of merge sort?

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

What is the worst-case time complexity of quicksort?

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

What does it mean that a problem has optimal substructure?

1. AThe problem has exactly one optimal solution, which every subproblem shares
2. BAn optimal solution can be built from optimal solutions of its subproblems
3. CThe problem can be solved in constant time
4. DEvery subproblem has the same size

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. BYes, because Big O is an upper bound and n² grows no faster than n³
3. CNo, because Big O must always state the exact growth rate of the function
4. DNo, because n³ is smaller than n² for large n

Which of these satisfiability problems is known to be solvable in polynomial time?

1. ACircuit satisfiability
2. BGeneral SAT on formulas in conjunctive normal form
3. C2-SAT, where each clause has at most two literals
4. D3-SAT, where each clause has exactly three literals

Which definition of the class NP is correct?

1. AProblems that no algorithm can solve
2. BDecision problems whose yes-answers can be verified in polynomial time given a certificate
3. CProblems that cannot be solved in polynomial time
4. DProblems that are not polynomial