# Computer science proving big-O definition

1. Oct 29, 2005

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

Last edited: Oct 29, 2005
2. Oct 29, 2005

### Hurkyl

Staff Emeritus
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?

3. Oct 29, 2005

### 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

4. Oct 29, 2005

### Hurkyl

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

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

5. Oct 29, 2005

### 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?

6. Oct 29, 2005

### Hurkyl

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

7. Oct 29, 2005

### KataKoniK

Alright, I will give that a try, thanks.