# Big-O

• July 15th 2008, 08:07 PM
Ramin_Shahab
Big-O
Hi everyone. Im kind of not seeing it with the follwing problem. Any suggestions is much appreciated.

Show that (x^2+1)/(x+1) is O(x)

I was thinking my first step would be
To use C= 1 and K=1

but I am stuck here
• July 15th 2008, 09:41 PM
Chop Suey
What is O(x)? What is C? What is K?

Can you write out the entire question?
• July 15th 2008, 10:01 PM
Mathstud28
Quote:

Originally Posted by Chop Suey
What is O(x)? What is C? What is K?

Can you write out the entire question?

It is Big Oh notation, it means that a function is bounded above by whatever. It is usually in discrete mathematics, I believe the K and C are the cosntants you must choose to show that some function is bounded by another. This might be a little bit strange if you have never seen it.
• July 15th 2008, 10:10 PM
Ramin_Shahab
Thats pretty much the whole question. (Thinking) But, Im still stuck on this and maybe its the fraction part thats throwing me off. Can anyone please give me somewhere to start?
• July 15th 2008, 11:01 PM
Isomorphism
Quote:

Originally Posted by Ramin_Shahab
Hi everyone. Im kind of not seeing it with the follwing problem. Any suggestions is much appreciated.

Show that (x^2+1)/(x+1) is O(x)

I was thinking my first step would be
To use C= 1 and K=1

but I am stuck here

We say $f(x) = O(g(x)),\text{ if }\exists M > 0, \forall x > x_0, |f(x)| < M|g(x)|$

So choose $M=1, \forall x > 1, \left|\frac{x^2 + 1}{x+1}\right| < |x|$
• July 15th 2008, 11:02 PM
CaptainBlack
Quote:

Originally Posted by Ramin_Shahab
Hi everyone. Im kind of not seeing it with the follwing problem. Any suggestions is much appreciated.

Show that (x^2+1)/(x+1) is O(x)

I was thinking my first step would be
To use C= 1 and K=1

but I am stuck here

For $x>0$ :

$\frac{x^2+1}{x+1} \le \frac{x^2+1}{x}$

and as for $x\ge 1,\ x^2+1 \le 2x^2$,

$\frac{x^2+1}{x+1} \le \frac{x^2+1}{x} \le \frac{2x^2}{x}=2x$

RonL