# Prove a lower bound

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?

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

• Let me note, that on linked definition is not implication which you have in inner square bracket. Commented Jul 23, 2021 at 8:06
• @zkutch The notation $\forall n > n_0, P(n)$ is an informal way of writing $\forall n, (n > n_0 \Rightarrow P(n))$. Commented Jul 23, 2021 at 14:25
• 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))$. Commented Jul 23, 2021 at 14:47
• @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. Commented Jul 23, 2021 at 15:16

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

• @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? Commented Jul 22, 2021 at 10:36
• Constructive critique is welcome, especially, when answer is correct. Commented Jul 22, 2021 at 10:55
• @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) Commented Jul 22, 2021 at 13:12
• 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. Commented Jul 22, 2021 at 15:43
• 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)$) Commented Jul 23, 2021 at 13:11

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.

• Hi! In our course we didn't dwell into the limit definition, and therefore we are required to solve it algebraically. Commented Jul 22, 2021 at 10:07
• @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.
– D.W.
Commented Jul 23, 2021 at 16:29
• @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. Commented Jul 23, 2021 at 16:35
• (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). Commented Jul 24, 2021 at 6:04
• (continuation for @Shufflepants) For each pair of functions participating in the definition using a fraction, a whole class of pairs with all possible subsequences "diluted" with zeros is lost. Immediately we lose such sets, for example, in which the boundary has a subsequence consisting of zeros. We lost for example $O(0)$, which, correct me please, if I am mistaken, only one consist with unique element. And Sorry for the long speech. Commented Jul 24, 2021 at 6:06

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

• My problem is more about how to find c,n_0, which confuses me in some exercises.. Commented Jul 24, 2021 at 15:19

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)\}$$