Big-O proof showing that t(n) is O(1)

191 Views Asked by At

Let t(n) = $\sqrt{n^2+100n} - n$

Show that $t(n)$ is $O(1).$

I tried solving this using the formal definition of O( ) but am not getting anywhere. Quite confused on how to tackle this question.

1

There are 1 best solutions below

4
On

Hint: $$ \begin{align} \sqrt{n^2+100 n} - n & = (\sqrt{n^2+100 n} - n) \frac{\sqrt{n^2+100 n} + n}{\sqrt{n^2+100 n} + n} \\ & = \frac{n^2+100 n-n^2}{\sqrt{n^2+100 n} + n} \\ & = \frac{100}{\sqrt{1+\frac{100}{n}} + 1} \quad \to \quad \frac{100}{2} = 50 \end{align} $$