I have to check if √log(n)=θ(log(√n)).
Following log rules I can write:
√log(n)=log(n)12
log(√n)=log(n12)=12log(n)
Looking at graphs I can see the O notation is correct but not the Ω.
I would appreciate some help at how to disprove this, as I am stuck for quite some time on it.
Thanks in advance
Answer
You want to prove that its not true that √log(n)=Ω(log√n). It is enough to prove that log√n√logn is unbounded. But this is true, simply because this ratio is
log√n√logn=√logn2→∞,
for n large.
No comments:
Post a Comment