HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Prove a lower bound

Submitted by: @import:stackexchange-cs··
0
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?

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

Context

StackExchange Computer Science Q#142545, answer score: 6

Revisions (0)

No revisions yet.