For the two functions f(n) and g(n), where $f(n) = n^{1/2}$ and $g(n) = 2^{(\log_2 n)^{1/2}}$, I am trying to determine whether $f$ is asymptotically bound below by $g$, i.e find whether there exists an N1 and a k1 > 0 such that:

$ f(n) >= k1 * g(n)$, for all n >= N1.

By taking the log of both $f(n)$ and $g(n)$ I got:

$f(n) = n^{1/2} = logn^{1/2} = 1/2*logn$.

$g(n) = 2^{(\log_2 n)^{1/2}} = log(2^{(\log_2 n)^{1/2}}) = (\log_2 n)^{1/2}log2$.

In trying to solve this I have:

$1/2logn >= k1 * (\log_2 n)^{1/2}log2$

Setting k1 to 1/2:

$1/2logn >= 1/2 * (\log_2 n)^{1/2}log2$

Dividing both sides by 1/2:

$logn >= (\log_2 n)^{1/2}log2$

Subtracting $(\log_2 n)^{1/2}log2$ from both sides:

$logn - (\log_2 n)^{1/2}log2 >= 0$

I can probably figure out whether there is any N1 such that the above is true for all n >= N1 by substituting values. However, I was wondering if there is any way to further simplify the above expression. In particular is there any way to get rid of the $(\log_2 n)^{1/2}$ entirely? I would prefer all the logs in the inequality to have the same base. Any insights are appreciated.

  • $\begingroup$ In my answer that you've accepted, I made a mistake which I've now corrected. In particular, I used $\log(ab) = \log(a) \log(b)$, which is what you've used as well, instead of the correct $\log(ab) = \log(a) + \log(b)$, when you take logarithms of both sides of the original inequality. I'm sorry for my mistake, but as you can see it does't change the overall result. $\endgroup$ Mar 4 '19 at 4:33

You could finish your work using $\log$, I assume to base $e$ but, in answer to your request of

I would prefer all the logs in the inequality to have the same base.

since $g(n)$ uses a base of $2$ and has a $\log$ to the base of $2$ in the exponent, it would likely be simplest & easiest to instead take the logs of both sides to base $2$ so you're then comparing the exponents of $f(n)$ and $g(n)$ to that base. As such, this would change trying to prove that there exists an $N_1$ and a $k_1 \gt 0$ such that

$$f(n) \ge k_1 \, g(n) \; \forall \; n \ge N_1 \tag{1}\label{eq1}$$

to finding, by taking $\log_2$ of both sides, a $k_2 = \log_2{k_1}$ such that

$$\log_2{f(n)} \ge k_2 + \log_2{g(n)} \; \forall \; n \ge N_1 \tag{2}\label{eq2}$$

Note that

$$\log_2{f(n)} = \log_2{n^{\frac{1}{2}}} = \frac{1}{2} \, log_2 n \tag{3}\label{eq3}$$ $$\log_2{g(n)} = \log_2{2^{(\log_2 n)^{\frac{1}{2}}}} = (\log_2 n)^{\frac{1}{2}} \tag{4}\label{eq4}$$

Substituting \eqref{eq3} and \eqref{eq4} into \eqref{eq2} gives

$$\frac{1}{2} \, \log_2 n \ge k_2 + (\log_2 n)^{\frac{1}{2}} \; \forall \; n \ge N_1 \tag{5}\label{eq5}$$

In this case, consider values of $m$ where $\frac{1}{2}m^2 \ge m$. Multiplying both sides by $2$, moving $2m$ to the LHS and factoring gives $m\left(m - 2\right) \ge 0$. This is true for all $m \ge 2$. In this case, if we let $m = (\log_2 n)^{\frac{1}{2}}$, we can see that having $k_2 = 0$ and since $(\log_2 16)^{\frac{1}{2}} = 2$, we can use $N_1 = 16$. I believe you should be able to finish the rest.

Note if you had used your original idea of, I assume, the natural logarithm, it would just involve an extra factor by the change of logarithm base formula, i.e., $\log_a{x} = \cfrac{\log_b{x}}{\log_b{a}}$ to give in this case that $\log_2{n} = \cfrac{\log_e{n}}{\log_e{2}}$. Also, as I show, you would need to add the constant, not multiply by it. After that correction, this just results in an extra factor being used for $\log_2{n}$, plus you also have the $\log_e{2}$ factor, so it might change the $k_2$ constant you determine to use (but not necessarily the $k_1$ constant) and/or the value of $N_1$, as these values are not uniquely determined.


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.