Given the recurrence relation \(T(n) = T(n/3) + T(2n/3) + n\), what is the…

TS-SET (TG-SET) 2024

Given the recurrence relation T(n)=T(n/3)+T(2n/3)+nT(n) = T(n/3) + T(2n/3) + n, what is the asymptotic time complexity?

  1. A.

    O(n)O(n), since the recurrence relation divides the problem into smaller subproblems of linear size.

  2. B.

    O(nlog⁡n)O(n \log n), since it combines two subproblems with an additional linear term.

  3. C.

    O(n2)O(n^2), because the subproblem sizes lead to a quadratic complexity.

  4. D.

    O(nlog⁡log⁡n)O(n \log \log n), due to the combination of subproblem sizes and the linear additional work.

Attempted by 6 students.

Sign up free to check your answer

Sign up free

Explore the full course: Uppsc Polytechnic Lecturer 2025 Cs

Loading lesson…