The GATE Grind

GATE 2009 CS – Question 35

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice

For a constant c, $T(n)=n$ for $n\le3$, and $T(n)=T(n/3)+cn$ otherwise. What is the time complexity?

  1. $\Theta(n)$
  2. $\Theta(n\log n)$
  3. $\Theta(n^2)$
  4. $\Theta(n^2\log n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $\Theta(n)$

Explanation

We are sorry we couldn't write detailed soluition for this, we are working on it!, please consider asking your own AI, its just 2-3 clicks with very minimum effort

More Asymptotic Analysis and Time/Space Complexity questions

All Asymptotic Analysis and Time/Space Complexity questions →