Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

$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|cite|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|cite|improve this answer
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


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.