Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How can I prove big-O relation between $f=\log_2(\log_2 n)$ and $g=\sqrt{\log_2 n}\,$?

I want to find the constants, $c, N$ such that $\ g(x) \leq cf(x)$ for all $x>N$.

share|improve this question
1  
First you can find when $\log_2\log_2 N=\sqrt{\log_2 N}$. What happens if you take $x>N$ after that? –  Ian Coley Mar 20 '13 at 16:36
    
A useful result, if $\lim_{n\to \infty} \frac{g(n)}{f(n)}=a$, then $g=O(f)$. –  Mhenni Benghorbal Mar 20 '13 at 16:49
2  
As an additional comment, you need only check the relation between $\log_2x$ and $\sqrt x$. You may solve for $c,N'$ in this case let $N=2^{N'}$. –  Ian Coley Mar 20 '13 at 16:53
    
You can't. Did you mean $f(x) \le c g(x)$? –  Aryabhata Apr 3 '13 at 9:06
    
@FrankMcGovern I fail to see the point of solving $\log_2x=\sqrt{x}$. –  Did Apr 3 '13 at 9:26

1 Answer 1

The derivative of the usual logarithm function is less than $1$ on $(1,+\infty)$ hence $\ln x\leqslant x-1$ on $x\geqslant1$. This implies $\log_2x\leqslant2x$ on $x\geqslant1$. Since $\log_2x=2\log_2\sqrt{x}$, $\log_2x\leqslant4\sqrt{x}$ on $x\geqslant1$.

Appplying this to $x=\log_2n$, one sees that $f(n)\leqslant4g(n)$ for every $n\geqslant2$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.