CODEWITHSUNDEEP
algorithmbig-o
user1253637
user1253637

Reputation: 237

Which function grows faster lg( √n ) vs. √ log n

Which function grows faster :lg( √n ) vs. √ lg n?

When I did the calculations, I get lg (√n) is faster. Is this correct?

Upvotes: 2

Views: 2496

Answers (3)

Murat Derya Özen
Murat Derya Özen

Reputation: 2154

You are comparing

(1) lg( √n ) = lg( n ^ (1/2) ) = (1/2) * lg( n )

and

(2) √ log n = (√ lg n) / (√ lg 10)

Drop out the constants and that leaves us lg( n ) and √ lg n. Clearly, the first one is growing faster.

As a side note, logarithm of A in base B is equal to the logarithm of A in base X divided by the logarithm of B in base X, where X is a valid value as a logarithm base.

Upvotes: 1

Bill the Lizard
Bill the Lizard

Reputation: 405765

As mentioned in the comments, I usually graph two functions if I'm unsure which one grows faster. Normally you'd graph them for values of n that are around your expected range of inputs, but in this case you can see that lg (√n) does grow faster for even small values of n.

Function Graph

Note: The graph above assumed a base of 2 for lg and a base of 10 for log.

Upvotes: 2

Ted Hopp
Ted Hopp

Reputation: 234807

Your calculations are correct. lg (√n) = lg (n1/2) = lg(n) / 2, which grows as (√ log n)2

Upvotes: 6

Related Questions