I apologize in advance for my mathematical incompetence, but I have a hard time to solve that task. I need to prove that $ 0.01n^2-100n = Θ(n^2) $. I think, based on definitions, and other tasks that I understand how to prove $O$, $Ω$ and $Θ$, at least on simpler examples.
The defitinion: $c1 > 0$, $c2 > 0$, $n$ is a natural number: $0 ≤ c1*g(n) ≤ f(n) ≤ c2*g(n)$
Here I have two main issues:
- Firstly, I think that the upper bound could be only $ n $.
$0.01n^2-100n ≤ 1n$
when we have for example $n = 1$ (knowing that $n$ by the definition needs to be a natural number, and $c1$ needs to be $> 0$ ), so we have something that is true:
-99.99 ≤ 1
whatever $ n $ and $ c2$ I think of the above equation is true. So we don't really need $n^2$ here...
and second thing:
2) How I can choose the lower bound so that it can be $ ≤ $ than $ 0.01n^2-100n $ when my $c1$ needs to be $> 0$. I cannot put here anything that could be more negative than $0.01n^2-100n$.
Thanks for any hints!
We have that
$$0.001 n^2\le0.01n^2-100n\le 0.01n^2$$
indeed
$$0.001 n^2\le0.01n^2-100n \implies 0.0099n^2\ge100n \implies n\ge \frac{100}{0.0099}$$