Need help proving an asymptotic notation

Question

I am studying for National Olympiad for informatics and one of the questions was about asymptotic notations. The equation was this:

$$ log5^+4∈Ω() $$

I am a high school student and haven't learned logarithm yet; but I tried my best, only to find out it was wrong:

$$ log 5^n + log 10^4 ≥ cn $$

$$ 5^n.10^4 ≥10^{cn} $$

$$ 5^n.10^4>=5^{cn}.2^{cn} $$

Here, I thought that $ 5^{cn} $ is always bigger than $5^n$, and $2^{cn}$ is bigger than $10^4$ for a value of n big enough. So I came to a conclusion that this equation was false. But then I learned that it was actually true. Why is that?

Answer 1

Remember $\Omega$ notation implies there exists some $c > 0$ such that your inequality holds.

Your inequality can be written as $$\left(\frac{5}{10^c}\right)^n \ge 10^{-4}.$$ If $0 < c \le \log 5$ is small enough, we have $5/10^c > 1$, so the inequality holds for all large $n$.

Answer 2

You have to show that $$ \log(5^n) + 4 = n\log(5) + 4 \ge cn $$ for some constant $c$ as long as $n$ is large enough.

The expression on the left defines a straight line with slope $\log(5)$ and a positive $y$-intercept. Any less steep line through the origin (that is, any $c < \log(5)$) will always be below.

Note: I haven't had to argue that the inequality is true for $n$ large enough. It's true all the time. That makes me suspicious - either the problem is not a good one or I have made a mistake. If when solving a problem you find an answer that seems too simple it's wise to wonder.