Algorithms & complexity worksheet with answers

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

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

What does the average-case running time describe?

1. AThe middle value between the best-case and worst-case running times
2. BThe time for an input of average length
3. CThe expected time over a given distribution of inputs of size n
4. DThe time on the most common computer

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

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

What is the time complexity of: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

What does the recurrence T(n) = T(n − 1) + O(1) solve to?

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

A greedy algorithm:

1. ATries every possible solution
2. BAlways gives the optimal solution
3. CMakes the locally best choice at each step
4. DUses only recursion

Which definition of the class P is correct?

1. AProblems that can be solved in parallel
2. BDecision problems solvable by a deterministic algorithm in polynomial time
3. CProblems that need exponential time on every computer
4. DProblems whose solutions can be checked but never found in polynomial time

What did the Cook–Levin theorem establish?

1. AEvery NP problem can be solved in exponential time
2. BP is not equal to NP
3. CThe Boolean satisfiability problem (SAT) is NP-complete
4. DThe halting problem is undecidable