Friday, December 21, 2018

logarithms - sqrtlogn vs logsqrtn




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)=Ω(logn). It is enough to prove that lognlogn is unbounded. But this is true, simply because this ratio is
lognlogn=logn2,


for n large.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...