2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$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)})$ ?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Nejc Nov 17 '12 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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