1

I'm learning the master method and am looking for help on how to best approach comparing two functions asymptotically. More specifically, I have:

T(n) = 3T(n/5) + lg^2(n)

and so by the Master method I am comparing

n^(log_5(3))  with  lg^2(n)

I tried graphing the two functions and it looks like lg^2(n) is larger. But the solution says otherwise. (ie. Case 1.) Can anyone help clear the fog for me? Thanks.

zzz2991
  • 419

1 Answers1

0

Define $u_n=(\log_53)\cdot\log n$ and $v_n=2\cdot\log\log n$, then $n^{\log_53}=\mathrm e^{u_n}$ and $(\log n)^2=\mathrm e^{v_n}$. Can you show these identities? Next, can you compare $u_n$ and $v_n$ when $n\to\infty$? What does this tell you about $n^{\log_53}$ and $(\log n)^2$ when $n\to\infty$?

Did
  • 279,727