patternMinor
Prove a lower bound
Viewed 0 times
lowerprovebound
Problem
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 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?
Solution
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$.
$$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$.
Context
StackExchange Computer Science Q#142545, answer score: 6
Revisions (0)
No revisions yet.