# Question about asymptotic notation with logs of different bases

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.

• 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. 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.