5
$\begingroup$

Prove: $n^{5}-3n^{4}+\log\left(n^{10}\right)∈\ Ω\left(n^{5}\right)$.

I always get stuck in these types of questions, where there is a $"-(xy^{z})"$ in the expression. Whenever I see the solutions for these type of questions, I can't identify a single method that works every time and it's frustrating. How do I approach these types of questions?

$\endgroup$
4
$\begingroup$

Definitions

I'm using the definition of big-omega from Wikipedia and making it more explicit:

$$\left[ f(n) \in \Omega(g(n)) \right] \:\Longleftrightarrow\: \left[ \exists k \in \mathbb{R}^+, \exists n_0 \in \mathbb{N}, \forall n \in \mathbb{N}, \left[(n > n_0) \Rightarrow (f(n) \ge k \cdot g(n)) \right] \right]$$

In your statement you have $f(n) = n^5 - 3n^4 + \log(n^{10})$, and $g(n) = n^5$.

Intuitions

As $n$ gets larger, $f(n)$ essentially behaves like $n^5$ (which matches $g(n)$). This is because both the $-3n^4$ and $\log(n^{10})$ terms grow more slowly (see big-O theory). So the value of $k$ to satisfy the big-omega definition should be somewhere around $1$.

We (probably) can't choose $k = 1$ because $n^5 - 3n^4 < n^5$ for all $n > 0$, which means $f(n) < k \cdot g(n)$. We can disregard the $\log(n^{10})$ term because it grows slower than $-3n^4$. So we'll choose some $0 < k < 1$.

Solution

Let's choose $k = \frac{1}{2}$. (Actually any $k$ slightly less than $1$ will also work.)

Solve for the break-even point of $n^5 - 3n^4 = k \cdot n^5$, and we get $n = 6$. Choose $n_0 = 6$.

Now to confirm: Is it true that for all $n > 6$, we have $n^5 - 3n^4 \ge \frac{1}{2} n^5$? Yes, because:

$n > 6$ (left side of implication)
$\Rightarrow\: n \cdot n^4 > 6 \cdot n^4$ (multiply by $n^4$)
$\Rightarrow\: n^5 > 6n^4$ (simplify)
$\Rightarrow\: \frac{1}{2} n^5 > \frac{1}{2} 6n^4$ (multiply by $\frac{1}{2}$)
$\Rightarrow\: \frac{1}{2} n^5 > 3n^4$ (simplify)
$\Rightarrow\: \frac{1}{2} n^5 - 3n^4 > 3n^4 - 3n^4$ (subtract $3n^4$)
$\Rightarrow\: \frac{1}{2} n^5 - 3n^4 > 0$ (simplify)
$\Rightarrow\: \frac{1}{2} n^5 - 3n^4 + \frac{1}{2} n^5 > \frac{1}{2} n^5$ (subtract $\frac{1}{2} n^5$)
$\Rightarrow\: n^5 - 3n^4 > \frac{1}{2} n^5$ (simplify)
$\Rightarrow\: n^5 - 3n^4 \ge \frac{1}{2} n^5$. (weaken inequality)

Finally, because for all $n > 0$, we have $\log(n^{10}) > 0$, therefore $n^5 - 3n^4 + \log(n^{10}) > n^5 - 3n^4 \ge \frac{1}{2} n^5$.

Formal proof

Let $k = \frac{1}{2} \in \mathbb{R}^+$.
 Let $n_0 = 6 \in \mathbb{N}$.
  Let $n \in \mathbb{N}$ be arbitrary.
   Assume $n > n_0$.
    $\therefore n > 6$.
    $\therefore \log(n^{10}) > 0$.
    $\therefore \frac{1}{2} n^5 > 3n^4$.
    $\therefore n^5 - 3n^4 > \frac{1}{2} n^5$.
    $\therefore n^5 - 3n^4 + \log(n^{10}) \ge \frac{1}{2} n^5$.
    $\therefore f(n) \ge k \cdot g(n)$.
   $\therefore (n > n_0) \Rightarrow (f(n) \ge k \cdot g(n))$.
  $\therefore \forall n \in \mathbb{N}, \left[ (n > n_0) \Rightarrow (f(n) \ge k \cdot g(n)) \right]$.
$\therefore \exists n_0 \in \mathbb{N}, \forall n \in \mathbb{N}, \left[ (n > n_0) \Rightarrow (f(n) \ge k \cdot g(n)) \right]$.
$\therefore \exists k \in \mathbb{R}^+, \exists n_0 \in \mathbb{N}, \forall n \in \mathbb{N}, \left[ (n > n_0) \Rightarrow (f(n) \ge k \cdot g(n)) \right]$.
$\therefore f(n) \in \Omega(g(n))$.

$\endgroup$
4
  • $\begingroup$ Let me note, that on linked definition is not implication which you have in inner square bracket. $\endgroup$ – zkutch Jul 23 at 8:06
  • $\begingroup$ @zkutch The notation $\forall n > n_0, P(n)$ is an informal way of writing $\forall n, (n > n_0 \Rightarrow P(n))$. $\endgroup$ – Nayuki Jul 23 at 14:25
  • $\begingroup$ Of course, and I can delete my comment, if you like, but look carefully, please - it is not same with $(\forall n \gt n_0) (n > n_0 \Rightarrow P(n))$. $\endgroup$ – zkutch Jul 23 at 14:47
  • $\begingroup$ @zkutch I don't understand your most recent comment. I never wrote that logic phrase, and it doesn't make sense because $n$ is not in scope in the second set of parentheses. I still don't understand if you have a problem with my use of notation, actual difference in logic, or something else. $\endgroup$ – Nayuki Jul 23 at 15:16
6
$\begingroup$

Let me suggest direct simple solution: definition of $\Omega$ contains $2$ bound variables $c$ and $N$. In simple cases, as is in OP, we can choose one and solve second from expression obtained from definition. Obviously for left side we need constant less then one, so taking, for example, $c=\frac{1}{10}$ we have $$n^{5}-3n^{4}+\log\left(n^{10}\right) \geqslant \frac{1}{10} n^{5}$$ which gives $$9n^{5} \geqslant 30n^{4}-10\log\left(n^{10}\right) $$ It is enough to find $N$ for inequality $9n^{5} \geqslant 30n^{4}$, which gives $N= \left\lceil \frac{30}{9} \right\rceil$.

$\endgroup$
10
  • 1
    $\begingroup$ @MathCurious. It is not assumption but obtaining definition: we need to choose some constant $c\geqslant 0$ and choose $N \in \mathbb{N}$ for which $n \gt N$ gives required inequality. I show how to choose $c$ and asked: can you find $N$ now or you would like me to make it? $\endgroup$ – zkutch Jul 22 at 10:36
  • 1
    $\begingroup$ Constructive critique is welcome, especially, when answer is correct. $\endgroup$ – zkutch Jul 22 at 10:55
  • 2
    $\begingroup$ @nir shahar. It is not so: as you, sure, know definition of $\Omega$ contains $2$ bound variables $c$ and $N$. In simple cases, as is in OP, we can choose one and solve second from expression obtained from definition. First inequality have $c$, but have not $N$, so it is not exactly "what we are required to show", as you wrote. Let me repeat, it lacks $N$. So it is not assumption, but finding $N$, after having $c$. (continuing) $\endgroup$ – zkutch Jul 22 at 13:12
  • 2
    $\begingroup$ I still think that it is your perception @nir shahar, to understand the first inequality as an assumption. There was only a solution of inequality, and even if you did not understand something, in my firm belief, it was more correct to just ask. It's always better to get it straight and only then vote. Anyway, I edit it. $\endgroup$ – zkutch Jul 22 at 15:43
  • 1
    $\begingroup$ Nayuki’s answer below takes a similar approach. It’s about solving for the required constants by choosing a reasonable value for one and making the inequality work for the other. It’s a “working backward” approach—to write the proof, you then have to reverse a bit of the logic (instead of “choose c and find N to solve the inequality”, you get “let c and N be x and y, then the (proposition containing the) inequality holds and satisfies the definition of $\Omega(\cdot)$) $\endgroup$ – D. Ben Knoble Jul 23 at 13:11
5
$\begingroup$

Just apply the definition. So in this case, we must have that $\lim_{n \to \infty} f(n) / g(n) > 0$ in order for $f(n) = \Omega(g(n))$.

Let's plug in what you have and observe that

$$\lim_{n \to \infty} \frac{n^{5}-3n^{4}+\log(n^{10})}{n^5} = 1 > 0.$$

This completes the proof.

$\endgroup$
9
  • 1
    $\begingroup$ Hi! In our course we didn't dwell into the limit definition, and therefore we are required to solve it algebraically. $\endgroup$ – MathCurious Jul 22 at 10:07
  • $\begingroup$ @MathCurious, if you have constraints, we ask you to list them in the question. Be prepared that folks might answer based on the information in the question. Also, it's worth knowing that part of our mission is to build up an archive of questions and answers that will be useful not only to you but to others as well, so people might answer based on what they will expect will be useful not only to you but to others as well. $\endgroup$ – D.W. Jul 23 at 16:29
  • $\begingroup$ @MathCurious time complexity is a fundamentally limit based concept. It doesn't even make sense without limits which is why the very definition is limit based. And you can solve many limits algebraically. Perhaps to turn this answer into one acceptable for your class, you would just need to algebraically prove the limit does indeed equal 1 as Juho has assumed was trivially true. $\endgroup$ – Shufflepants Jul 23 at 16:35
  • $\begingroup$ @Shufflepants. From the beginning, I want to say that I completely agree with D.W. in this case, since it is impossible to answer a constantly changing question. On the other hand, it often happens that a person, having received an answer, clarifies the question. In this case, I think it is better to create a new question or write a separate addition/appendinx to the old one. I am absolutely sure that Juho would have written a different answer with a restriction from the very beginning. But let me point out that defining based limit is not at all fundamental (continuing) $\endgroup$ – zkutch Jul 24 at 5:59
  • $\begingroup$ (continuation for @Shufflepants) The vast majority of textbooks and monographs, I work with, are, as well as en.wikipedia.org/wiki/Big_O_notation or en.wikipedia.org / wiki / Time_complexity, based out as a two-factor constraint. And the main thing here is not even in the limit, which must be understood as limit superior, but in the use of a fraction. (continuing). $\endgroup$ – zkutch Jul 24 at 6:04
1
$\begingroup$

With small $n$ Big $\Omega$ it is just about useless and it's the hidden constants, so we suppose $n\to \infty$. At this situation, the term $n^5$ dominate other terms, and we can conclude that $n^5=\Omega(n^5)$.

Note that, if number of functions are constant ( in the below $k$ is constant) that has below form: $$f_1(n)+\dots+f_k(n)$$ and suppose $f(n)$ is a term that dominate other:

$$f(n)=\max\{f_1(n),\dots,f_k(n)\}$$

$\endgroup$
1
$\begingroup$

Here is a quick formal proof without limits. Choose $c=\frac{1}{4}$ and $n_0=4$. For $n \ge n_0$: $$ n^{5}-3n^{4}+\log n^{10} > n^5 - 3n^{4} = n^4 \cdot (n-3) \ge n^4 \cdot \frac{n}{4} = \frac{n^5}{4} =c n^5, $$ where we used the inequality $n-3 \ge \frac{n}{4}$ or, equivalently, $\frac{3}{4}n \ge 3$.

$\endgroup$
1
  • $\begingroup$ My problem is more about how to find c,n_0, which confuses me in some exercises.. $\endgroup$ – MathCurious Jul 24 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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