Computer science proving big-O definition (1 Viewer)

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

I have two questions here.
I must prove that [tex]f(n) = 100n^2 + 5n + 10[/tex] is in big-O of [tex]g(n) = n^3 - 100n^2[/tex]
I already found a constant [tex]c[/tex] and an [tex]n[/tex] that satisfies the condition such that [tex]f(n) \leq c * g(n)[/tex]. Let [tex]c = 1[/tex] and [tex]n = 201[/tex].
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 [tex]f[/tex] in big-O of [tex]g[/tex] then [tex]|f - g|[/tex] in big-O [tex]g[/tex]
 
Last edited:

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,829
14
I assume you meant to say that c=1 and n=201 satisfy the condition that

[tex]\forall m \geq n: f(m) < c * g(m)[/tex]

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?
 
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 [tex]g'(n) - f'(n) = 0[/tex] 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

Staff Emeritus
Science Advisor
Gold Member
14,829
14
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?
 
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

Staff Emeritus
Science Advisor
Gold Member
14,829
14
Probably. But if you said what you're trying to do, it might help you organize it into a proof.
 
Alright, I will give that a try, thanks.
 

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top