0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is really simple. Just look up the definitions of $O(n)$ and $\Omega(n)$ $\endgroup$ – lox Apr 15 at 14:49
  • $\begingroup$ @lox i can see it's simple, but in fact we need to prove it finding a constant $C$ and a $n_0$ large enough for this condition to be true. $\endgroup$ – joann2555 Apr 15 at 14:52
  • $\begingroup$ which bound do you have problems with? upper or lower? $\endgroup$ – lox Apr 15 at 15:04
  • $\begingroup$ @lox upper bound $\endgroup$ – joann2555 Apr 15 at 15:46
  • $\begingroup$ There is an answer below. If you understand, try as an exercise proving the same but for $27log^2(n)+\sqrt{n}$ $\endgroup$ – lox Apr 15 at 15:51
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't see how this answers the question. You're basically just asserting that $\log n$ is a lower-order term with respect to $\sqrt{n}$ so obviously $\log n + \sqrt{n}=\Theta(\sqrt{n})$. That's not a proof. $\endgroup$ – David Richerby Apr 15 at 19:20
  • $\begingroup$ @DavidRicherby this is a guide to a proof. $\log n$ is a lower order term with respect to $\sqrt{n}$. This can be proven with limits as I suggested. I mean, the whole thing could be proven with limits, but this is a method to get $c$ and $n_0$ as they ask in the comments. If you just want a proof that a log function is asymptotically smaller than a polynomial, see here or it's just a duplicate question here. If the real question is how to compare $\log n$ and $\sqrt{n}$, this should be stated. $\endgroup$ – ryan Apr 15 at 19:28
  • $\begingroup$ But proving it is the whole question! We can see that it's a lower-order term from the fact that it disappears in the big-Theta. $\endgroup$ – David Richerby Apr 15 at 19:30
  • $\begingroup$ If that is the whole question, then I would think this is just a duplicate. $\endgroup$ – ryan Apr 15 at 19:35
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ And what are the values of $c$ and $n_0$ then? He said in the comments that he need those values. Moreover, using l'Hopital seems a huge overkill, since it is a nontrivial result of analysis. I honestly don't see how it can be better than using the inequality $\log x < x$ for $x > 0$. $\endgroup$ – Hilder Vítor Lima Pereira Apr 15 at 21:37
  • $\begingroup$ the constant given in your answer seems to work well enough to me $\endgroup$ – lox Apr 16 at 8:23
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ OK but I think you need to prove that $\log n_0 < \sqrt{n_0}$ implies that $\log n < \sqrt{n}$ for all $n\geq n_0$. If you're just going to assume that $\log n = o(\sqrt{n})$ then the answer to the whole question is basically "It's obvious." $\endgroup$ – David Richerby Apr 15 at 19:18
  • $\begingroup$ @DavidRicherby well, I don't know if he really needs to prove this, since the answer to that kind of question usually proceeds as I did (one just uses obvious relations between the functions, as the fact that the graph of $\log n$ is below the one of $\sqrt n$ for all $n \ge 1$). But even if he wants to prove it "more formally", it is still trivial, since $\log n = \log{(\sqrt n \sqrt n)} = 2\log{\sqrt n}$ and we know that $\log{x} < x$, thus, we have the bound $27 \log n + \sqrt n \le 27 \cdot 2 \sqrt n + \sqrt n$ ... $\endgroup$ – Hilder Vítor Lima Pereira Apr 15 at 19:42
  • 1
    $\begingroup$ If you're allowed to say "obvious relations betwen the functions" then the whole answer is "It's obvious", which clearly isn't what's intended. $\endgroup$ – David Richerby Apr 15 at 19:53
  • $\begingroup$ @DavidRicherby What is considered obvious or not, what can already be used without proof or not, depends on the level and on the goals of the course... It is totally normal to let the students use that $\log n < \sqrt n$ (for instance, simply by looking at the graphs) and still ask them to find $c$ and $n_0$. But if he thinks he is not allowed to do this, then he can use other easy bounds, as I showed on my first comment. Hence, in both cases, I answered the question $\endgroup$ – Hilder Vítor Lima Pereira Apr 15 at 20:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.