Correct way to prove Big O statement

by R22 T22   Last Updated January 14, 2018 13:20 PM

From polynomial exercises e.g. $x^2$ + $5x$ +3 = O($x^2$). The method used was to set n≥k=1, knowing that $x^2$ + $5x^2$ + $3x^2$ was larger and then working out c.

How would you approach a question like $\frac{N}{N+ O(1)}$ = 1 + O($\frac{1}{N}$ ).

I've read alot of the other posts and some random uni lecture notes and just got more confused. When do we use limits to prove these statements? I also read how the "limit proof" for big O wasn't always applicable because some statements didn't have limits.

I made my own dodgy way of solving this which treated this as pretty much a LHS RHS statement.....



Answers 1


One may use $$ \frac1{1+x}=1-x+\frac{x^2}{1+x}=1+O(x),\quad \text{as}\quad x\to0, \tag1 $$ then observing that, as $N \to \infty$, by dividing numerator and denominator by $N$, $$ \frac{N}{N+O(1)}=\frac1{1+O(1/N)} $$ one gets $$ \frac{N}{N+O(1)}=\frac1{1+O(1/N)}=1+O\left(\frac1N\right)\tag2 $$ where we have used $(1)$ in the last step.

Olivier Oloa
Olivier Oloa
January 14, 2018 13:03 PM

Related Questions


How to derive algorithm recurrence?

Updated October 10, 2017 02:20 AM


Recurrence relation with θ

Updated August 01, 2017 05:20 AM

Comparing two algorithms for the LCS-problem

Updated November 07, 2017 01:20 AM