Math Is Fun Forum

Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

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

azair
Member Registered: 2013-01-08
Posts: 5

Big O Notation calculation.

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.

=>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)

☁ ♪ ☁☁♪♫☁
♫☁☁♪ ☁
❄ Music in the Sky ❅

Offline

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

bobbym
bumpkin From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Big O Notation calculation.

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.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

azair
Member Registered: 2013-01-08
Posts: 5

Re: Big O Notation calculation.

thanks (:

☁ ♪ ☁☁♪♫☁
♫☁☁♪ ☁
❄ Music in the Sky ❅

Offline

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

bobbym
bumpkin From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Big O Notation calculation.

Hi;

You are welcome.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline