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.
Best Answer
You could finish your work using $\log$, I assume to base $e$ but, in answer to your request of
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.