Big O Notation calculation.

azair · 2017-03-21 17:58:03

Help me!
Given an equation f(n) = 3n²-100n+6
How can you prove that f(n) = O(n²). Definition for O → |f(n)| <= c* |g(n)|.

My professor has taken c=3 and nₒ=34. So if n > nₒ = 34 → we can get rid of the absolute values. → |f(n)|=f(n). ... ... ...

>>>My question is, how did he get the c as 3 and nₒ as 34? Is it taken randomly??? or is it this way???:

3n²-100n = 0 (ignoring 6[c as standalone constant])
3n² = 100n
n = 100/3 = 33.333333 ≈ 34.
Is this correct??? Please advice.

=>Also proving f(n) = O(n³) , we are taking c = 1 and nₒ = 34. Why is c=1 here??

Thanks in advance and regards. (:

Last edited by azair (2017-03-21 18:13:40)

bobbym · 2017-03-21 21:02:03

Hi;

For one thing it looks like it can be done by inspection.

Big O Notation defines the behavior of a function as it approaches some value. Often, we say infinity, but generally "an arbitrarily large number" is sufficient.

It is clear that as n gets large the n^2 term is going to drown out the other terms. So we can say by inspection that O(f(n)) == O(n^2)

Or maybe you could try to show a bit more rigorously.

But this looks like overkill to me.

You might pick up a few hints on how engineers view this problem from here:

http://stackoverflow.com/questions/1513 … -fn-is-o2n

One of them uses a method similar to your professor.

azair · 2017-04-15 05:37:57

thanks (:

bobbym · 2017-04-15 06:03:00

Hi;

You are welcome.

Math Is Fun Forum

#1 2017-03-21 17:58:03

Big O Notation calculation.

#2 2017-03-21 21:02:03

Re: Big O Notation calculation.

#3 2017-04-15 05:37:57

Re: Big O Notation calculation.

#4 2017-04-15 06:03:00

Re: Big O Notation calculation.

Board footer