For parameters a and {b}, both of which are { }^{\omega(1),} {T}( {n})= {T}( {n}^{1 {/ }{a}})+1, and {T}( {b})=1 . Then {T}( {n}) is:

Correct Answer is : Θ(logalog0n)

GATE Computer Science (CS) 2020 Solved Papers

Question : 26 of 65

Marks: +1, -0

For parameters a and

{b}

, both of which are

{ }^{ω(1),} {T}( {n})= {T}( {n}^{1 {/ }{a}})+1

, and

{T}( {b})=1 .

Then

{T}( {n})

is:

Solution:

T(n)=T(n^{\;{1}/{a}})+1 \;\& T(b)=1

T(n^{\;{1}/{a}})=T(n^{\;{1}/{a}})^{\;{1}/{a}})+1 \;\& T(b)=1

=(T(n^{\;{1}/{a^{2}}})+1)+1

T(n^{\;{1}/{a^{2}}})=(T((n^{\;{1}/{∂^{2}}})^{\;{1}/{a}})+2)+1

=T n^{\;{1}/{3^{3}}})+3

\;\; T(\;{1}/{n^{ {k}^{k}}})+ {K}

⇒ \log _{a} \log _{b} n

⇒ O(\log _{a} \log _{b} n)

Go to Question:

Prev Question

Next Question