# Big O Notation

1. Feb 20, 2006

### hain

I'm having some trouble with this discrete question:

Find the least natural number n such that
√(x² + x³ + 3) is O(xⁿ).

With the value of n that you have found, is it true that
xⁿ is O( √(x² + x³ + 3) )?

Can anyone help?

2. Feb 20, 2006

### HallsofIvy

Staff Emeritus
Well, starting with the definition of "O" would be a good idea. What is it?

3. Feb 20, 2006

### hain

http://en.wikipedia.org/wiki/Big-O_notation

I'm able to determine n in simpler cases, but I have no idea how to approach the root of this polynomial.

4. Feb 20, 2006

### Hurkyl

Staff Emeritus
These are easy: they're close enough to polynomials for the purposes asymptotic analysis. How would you do it if it was a polynomial?

5. Feb 20, 2006

### hain

Err, typing this stuff out is difficult. Here's an example with polynomials: http://en.wikipedia.org/wiki/Big-O_notation#Example . It's images so it's easy to read.

6. Feb 21, 2006

### HallsofIvy

Staff Emeritus
Why would you want to find a root? What is
$$\frac{\sqrt{x^2+x^3+ 3}}{x^n}$$
?