1. ## 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

2. What is O(x)? What is C? What is K?

Can you write out the entire question?

3. 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.

4. Thats pretty much the whole question. But, Im still stuck on this and maybe its the fraction part thats throwing me off. Can anyone please give me somewhere to start?

5. 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|$

6. 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