Monday, 17 July 2017

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

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...