T(n)=2T( n)+1 for n>2, and T(n)=2 for 0<n≤2. Find its asymptotic order.

GATE 2017 CS (CS2) – Question 40

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

$T(n)=2T(\sqrt n)+1$ for n>2, and T(n)=2 for 0<n≤2. Find its asymptotic order.

$\Theta(\log\log n)$
$\Theta(\log n)$
$\Theta(\sqrt n)$
$\Theta(n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\Theta(\log n)$

Explanation

Set m=log₂n and S(m)=T(2ᵐ). Then S(m)=2S(m/2)+1 with constant-size base case, so S(m)=Θ(m) by the master theorem. Substitution back gives T(n)=Θ(log n), B. Equivalently the recursion tree has Θ(log n) leaves.

More Asymptotic Analysis and Time/Space Complexity questions

GATE 2017 CS (CS2) Q48 – Find the time complexity.
GATE 2012 CS (CS1) Q15 – Find the worst-case search time in a balanced BST with n2n elements.
GATE 2012 CS (CS1) Q28 – W(n) and A(n) are worst-case and average running times on inputs of size n. Which always…
GATE 2013 CS (CS1) Q40 – How many elements can heap sort sort in ( n) time?
GATE 2013 CS (CS1) Q41 – What is the asymptotic return value, rather than running time?
GATE 2011 CS (CS1) Q47 – Find increasing asymptotic growth order for f 1(n)=2n, f 2(n)=n3/2, f 3(n)=n 2n, f 4(n)=n…

All Asymptotic Analysis and Time/Space Complexity questions →