Computer science proving big-O definition

[KataKoniK]

I have two questions here.
I must prove that $$f(n) = 100n^2 + 5n + 10$$ is in big-O of $$g(n) = n^3 - 100n^2$$
I already found a constant $$c$$ and an $$n$$ that satisfies the condition such that $$f(n) \leq c * g(n)$$. Let $$c = 1$$ and $$n = 201$$.
However, I am stuck on showing/manipulating the algebra that this is true.

Second question:

How would you prove this? I know you use the triangle inequality, but I have no idea how to implement this. Any help would be great, thanks.

If $$f$$ in big-O of $$g$$ then $$|f - g|$$ in big-O $$g$$

 

[Hurkyl]

I assume you meant to say that c=1 and n=201 satisfy the condition that

$$\forall m \geq n: f(m) < c * g(m)$$

Intuitively, g(n) grows faster than f(n), right? Can you think of any algebraic way to capture this notion?



As for the other question, how far have you gotten in your attempt? Have you at least written down what you're assuming and what you're trying to prove?

 

[KataKoniK]

Hmm, I couldn't really think of an algebraic way of capturing that, but what I did was find the derivative of f and g. Then I solved for $$g'(n) - f'(n) = 0$$ and got n = 133.3 and -0.12. However, I do not know how to better show that f is less than c * g(n) for n >= 210.


btw, I solved the |f - g| is in big-O of g

 

[Hurkyl]

I couldn't really think of an algebraic way of capturing that,

I bet you have, and just haven't realized it yet.

Why did you solve g'(n) - f'(n) = 0 for n?

 

[KataKoniK]

Whoops, I meant that I solved for (f - g)' because we want to know when the function is >= 0 and not less than 0. Am I doing the right thing?

 

[Hurkyl]

Probably. But if you said what you're trying to do, it might help you organize it into a proof.

 

[KataKoniK]

Alright, I will give that a try, thanks.