Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Hopefully this is the right section. I need to prove that $2^{(log(n)^{1/2})}$ is $O(n^a)$. From the basic principle of Big-O notation, I know I need to find two numbers $c$ and $N$ so that $f(n) \le c\cdot g(n)$ for all values of $n \ge N$. In this case, $f(n)$ is $2^{(log(n)^{1/2})}$, and $g(n)$ is $n^a$.

The first problem in the set had me prove that $2^{n+a}$ is $O(2^n)$. For this problem, I had separated the $f(n)$ to $2^n \cdot 2^a$. I was guided by another user to set $c = 2^a$. This way, with $g(n) = 2^n$, $cg(n) = 2^a2^n$, which is obviously $\ge f(n)$, $2^{n+a}$, for all values of $n \ge 0$. This problem, however, I don't find as easy.

Could someone point me in the right direction? I've been trying to rearrange the problem and solve it for a while now.

share|improve this question

2 Answers 2

$n^a = \exp(a \ln n) = \exp(a \ln n \frac{\ln 2}{\ln 2}) = 2^{\frac{a \ln n}{\ln 2}}$. Can you prove that if $h(n) = O(k(n))$ then $2^{h(n)} = O(2^{k(n)})$ ?

share|improve this answer

It holds that $\log x^y=y\log x$. Hence we have $$2^{\log n^{1/2}}=2^{1/2 \log n}=(2^{\log n})^{1/2}=n^{1/2}=O(n^{1/2}).$$

So this is mostly about computing with logarithms, and not so much about the big-O notation.

share|improve this answer
2  
I am not quite sure, that by $log(n)^{1/2}$ he meant $log(n^{1/2})$. Maybe he actually meant $log^{1/2}(n)$. I think OP should clarify. –  Nejc Nov 17 '12 at 14:35

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.