Recurrence Relations · Application: Divide and Conquer

Lesson 8

Nikolai Chukhin · Alexander S. Kulikov

Problem. Mark the correct statements.

5 points

  1. If \(T(n) \le 5T(n/4)+O(n)\), then \(T(n)=O(n)\).

  2. If \(T(n) \le 5T(n/4)+O(n)\), then \(T(n)=O(n^{2})\).

  3. If \(T(n) \le 5T(n/4)+O(n^{2})\), then \(T(n)=O(n^{2})\).

  4. If \(T(n) \le 7T(n/2)+O(n^{2})\), then \(T(n)=O(n^{2})\).

  5. If \(T(n) \le 7T(n/2)+O(n^{2})\), then \(T(n)=O(n^{3})\).