Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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$.
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$.
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$.
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 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$.
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.
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$.
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)\}$$
