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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

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

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

☁ ♪ ☁☁♪♫☁

♫☁☁♪ ☁

❄ Music in the Sky ❅

Offline

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

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

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

thanks (:

☁ ♪ ☁☁♪♫☁

♫☁☁♪ ☁

❄ Music in the Sky ❅

Offline

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

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

Pages: **1**