Comparing logarithmic functions. Master Method I'm learning the master method and am looking for he

Micaela Simon

Micaela Simon

Answered question

2022-06-15

Comparing logarithmic functions. Master Method
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.

Answer & Explanation

Lamont Adkins

Lamont Adkins

Beginner2022-06-16Added 11 answers

Define u n = ( log 5 3 ) log n and v n = 2 log log n, then n log 5 3 = e u n and ( log n ) 2 = e v n . Can you show these identities? Next, can you compare u n and v n when n ?? What does this tell you about n log 5 3 and ( log n ) 2 when n ?

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?