How can i prove this asymptotic comparison? [duplicate]

Question

This question already has an answer here:

• Sorting functions by asymptotic growth 6 answers

This is an exercise that's part of my assignment, but it is optional and flagged as a "challenge". I would like to discuss its solution:

Prove that: $$ 27\log{n} + \sqrt{n} = \theta(\sqrt{n})$$

Clearly this is correct, because the dominant term ($\sqrt{n}$) is present in both sides. But i wasn't able to give a mathematic explanation why it's correct.

Answer 1

When it comes to instances like this, I prefer to think about conceptually "promoting" and "demoting" lower order terms.

For instance, if we wanted to upper bound:

$$f(n) = 32 + 11 \log_2 n + 5 n + 2 n^2$$

We know (by intuition or limits) that $n^2$ is the fastest growing term here. Thus, we should be able to bound $f(n)$ by $n^2$. By this, I mean we can find some constant $c$ such that $f(n) \leq c n^2$ for all $n \geq n_0$ (where $n_0$ is some initial starting value for $n$ where this inequality holds true). Note, that this is preciesly the definition of Big O.

Promoting lower order terms of $f(n)$ - Consider we can represent each lower order term by a constant $c_0$ times some function $h_0$ of $n$ (e.g. $c_0 \cdot h_0(n) = 11 \cdot \log_2 n$). For each lower order term, we will promote $h_0(n)$ to the highest order function of $n$, call it $h^*(n)$ and leave the constant the same.

Consider the lower order terms of our example: $\{32,\ 11 \log_2 n,\ 5n\}$ and the highest order term $2 n^2$. The promotions will go as follows:

$$\begin{align*} 32 & \mapsto 32 \cdot n^2\\ 11 \cdot \log_2 n & \mapsto 11 \cdot n^2\\ 5 \cdot n & \mapsto 5 \cdot n^2 \end{align*}$$

Let's assume $n_0$ is the first value of $n$ for which all lower order functions of $n$ are less than or equal to the highest order function of $n$. In our example we have:

$$\begin{align*} 1 & \leq n^2 & \forall n \geq 1\\ \log_2 n & \leq n^2 & \forall n \geq 1\\ n & \leq n^2 & \forall n \geq 1 \end{align*}$$

Thus we have found our $n_0 = 1$. Now we can replace the lower order terms in $f(n)$ with their promoted counterparts to get:

$$\begin{align*} f(n) & = 32 + 11 \log_2 n + 5 n + 2 n^2\\ & \leq 32 n^2 + 11 n^2 + 5 n^2 + 2n^2 & = 50 n^2 \end{align*}$$

With this he have found our $c = 50$. Thus we can conclude:

$$f(n) \leq 50 n^2 \quad \forall n \geq 1 \quad \implies f(n) = O(n^2)$$

For demoting lower order terms we simply remove them from the equation to get:

$$\begin{align*} f(n) & = 32 + 11 \log_2 n + 5 n + 2 n^2\\ & \geq 2n^2\\ & = 2n^2 \end{align*}$$

Thus we can conclude:

$$f(n) \geq 2 n^2 \quad \forall n \geq 1 \quad \implies f(n) = \Omega(n^2)$$

Then we clearly get:

$$f(n) = O(n^2) \land f(n) = \Omega(n^2) \implies f(n) = \Theta(n^2)$$

---

Typically, most of these operations are simple enough to just conclude $f(n) = \Theta(n^2)$ in one fatal sweep, though it does always help to determine $c$ and $n_0$ explicitly when you need to. Clearly, the $c$ we find here is a loose upper bound and you could usually restrict it further if you needed to.

At this point I am assuming you have a summation of functions that are monotone non-decreasing. You must be a bit more careful when you have decreasing lower order terms, but these are usually not a big problem.

Answer 2

Since it seems to be an unfulfilled clause in this discussion, let me add a quick proof that the following equations hold:

$ log(n) \leq \sqrt {n} $ for all $n \geq n_0$, where $n_0$ is some constant.

proof by L'Hospitals rule:

$$\lim_{n\to \infty } \frac{\log(n)}{\sqrt{n}} = \frac{\frac{1}{n}}{\frac{1}{2\sqrt{n}}} = \frac{2\sqrt{n}}{n}=\frac{2}{\sqrt{n}} \rightarrow 0$$

similarly:

$$\lim_{n\to \infty } \frac{\sqrt{n}}{\log(n)} = \frac{\frac{1}{2\sqrt{n}}}{\frac{1}{n}} = \frac{n}{2\sqrt{n}}=\frac{\sqrt{n}}{2} \rightarrow \infty$$

We proved $\lim_{n\to \infty } \frac{\log(n)}{\sqrt{n}}$ is $0$, which means essentially $ log(n) < \sqrt {n} $ for all $n$ sufficiently large, and also that $\lim_{n\to \infty } \frac{\sqrt{n}}{\log(n)}$ is $\infty$ therefore does not exist.

Answer 3

Find $c$ and $n_0$ for $\Omega$ and then find other $c$ and $n_0$ for $O$. This way, you prove that the function is both $\Omega(\sqrt n)$ and $O(\sqrt n)$, therefore, it is $\Theta(\sqrt n)$.

EDIT: I am changing the answer to get a bound from the well-known inequality $\log x < x$ for $x > 0$.

For $\Omega$: use that $\log n \ge 0$ for $n \ge 1$, which implies that $27 \log n \ge 0$ and then $27 \log n + \sqrt n \ge \sqrt n$. Therefore, you have $c = 1$ and $n_0 = 1$.

For $O$, notice that $\log n = \log(\sqrt n \sqrt n) = 2\log \sqrt n$.

Then, using that $\sqrt n > 0$ for $n \ge 1$ you have $\log \sqrt n < \sqrt n$, thus

$$27 \log n + \sqrt n \le 27 \cdot 2\sqrt n + \sqrt n = 55 \sqrt n.$$

Thus, you have $c = 55$ and $n_0 = 1$.