How would I find the asymptotic value for this function in big theta notation?

Question

$ \frac{5}{n} + log_3 n + 11√n $

Can someone please explain to me what steps I would do for this? I really don't understand what I should do to find the asymptotic value.

Answer 1

Let's look at the following function:

$$ f(n) = \frac{a}{n} + log_b(n) + c\sqrt{n} $$

(where $b > 1$)

I would do this in parts. First part, prove that $\frac{a}{n} \in O\left(\sqrt{n}\right)$, then prove that $\log_b(n) \in O\left(\sqrt{n}\right)$.

The first one is pretty easy:

\begin{align*} \left|\frac{a}{n}\right| \leq \alpha \sqrt{n} \leadsto a \leq \alpha n^{\frac{3}{2}} \\ \left|\frac{a}{\alpha}\right|^{\frac{2}{3}} \leq n \end{align*}

So, all we have to do is choose any positive $\alpha$ and then $n_0 \geq \left|\frac{a}{\alpha}\right|^{\frac{2}{3}}$.

The next one is more difficult and requires a little more reasoning:

\begin{align*} \left|log_b(n)\right| \leq \beta\sqrt{n} \leadsto n \leq b^{\beta\sqrt{n}} = \left(b^{\beta}\right)^\sqrt{n} \end{align*}

Lets simplify things by choosing $\beta$ such that $b^\beta = e \leadsto \beta\ln(b) = 1 \leadsto \beta = \frac{1}{\ln(b)}$

If we look at the function: $g(n) = e^\sqrt{n} - n$, then showing that the limit as $n$ tends towards infinity is positive infinity shows that there exists an $n_0$ such that for all $n > n_0$, $g(n) > 0$ and thus $\beta\sqrt{n} \geq \left|log_b(n)\right|$ for all $n \geq n_0$. So we need to show the following limit:

$$ \lim_{n \rightarrow \infty}\left(e^\sqrt{n} - n\right) \rightarrow +\infty $$

At first, we have an indeterminate limit because we have $\infty - \infty$, but simply dividing by $n$ can help:

$$ e^\sqrt{n} - n = n\left(\frac{e^\sqrt{n}}{n} - 1\right) $$

You can "easily" show that $\lim_{n\rightarrow \infty}\frac{e^\sqrt{n}}{n} \rightarrow +\infty$, which then gives $+\infty * +\infty \rightarrow +\infty$.

All of this means that there exists an $n_0$ such that for all $n > n_0$, $e^\sqrt{n} - n \geq 0 \implies e^\sqrt{n} \geq n \implies \beta\sqrt{n} \geq log_b(n)$.

You combine all of this to get:

$$ \alpha \sqrt{n} + \beta\sqrt{n} + |c|\sqrt{n} \geq \left|\frac{a}{n}\right| + \left|\log_b(n)\right| + c\sqrt{n} \\ \left|\frac{a}{n} + \log_b(n)+ c\sqrt{n}\right| \leq (\alpha + \beta + |c|)\sqrt{n} $$

$$ \forall n, n > n_0: \left|log_b(n_0)\right| \leq \beta\sqrt{n_0} \wedge n_0 \geq \left|\frac{a}{\alpha}\right|^{\frac{2}{3}} $$

Your Problem

Your problem is easier because you know $a$, $b$, and $c$. You can find the exact $\alpha$ that works and you can find the specific value of $n_0$ (through numerical methods) where $\log_3(n) = \sqrt{n}$.

That "easy" limit

We can use L'Hospital's Rule to find the limit:

\begin{align} \lim_{n \rightarrow \infty}\frac{e^\sqrt{n}}{n} =&\ \lim_{n\rightarrow\infty}\frac{\frac{1}{2\sqrt{n}}e^\sqrt{n}}{1}\\ =&\ \frac{1}{2}\lim_{n\rightarrow\infty}\frac{e^\sqrt{n}}{\sqrt{n}}\\ =&\ \frac{1}{2} \lim_{n\rightarrow\infty}\frac{\frac{1}{2\sqrt{n}}e^\sqrt{n}}{\frac{1}{2\sqrt{n}}} \\ =&\ \frac{1}{2}\lim_{n\rightarrow\infty}e^\sqrt{n} \rightarrow +\infty \end{align}

p.s. there was an easier way:

\begin{align*} \lim_{n\rightarrow\infty}\frac{e^\sqrt{n}}{n} =& \lim_{n^2\rightarrow\infty}\frac{e^n}{n^2} \\ =&\ \lim_{n^2\rightarrow\infty}\frac{e^n}{2n} \\ =&\ \frac{1}{2}\lim_{n^2\rightarrow\infty}\frac{e^n}{1} \rightarrow +\infty \end{align*}