GATE CS 2021 Set 1 – Question 36

Multiple choice 2 marks Question 36 2021

Question 36

MCQ 2 marks · −0.66 Algorithms

Consider the following recurrence relation:

\(T(n) = T(n/2) + T(2n/5) + 7n\) for \(n > 0\), and \(T(0) = 0\).

Which one of the following options is correct?

A \(T(n) = \Theta(n \log n)\) B \(T(n) = \Theta(n)\) C \(T(n) = \Theta(n^2)\) D \(T(n) = \Theta(\log n)\)

Answers and explanations are free — they just need an account.

GATE CS — Computer Science & IT 2021 Algorithms

Source: GATE 2021 Computer Science and Information Technology, Set 1, Q36 (question number approximate; option wording reconstructed)