Big-O complexity proof

84 Views Asked by At

I'm trying to prove that the function

$t(n) = \sqrt{n^2 - 10(n)} - n $

is equal to O(1) time complexity. I know that the function has a horizontal asymptote at 5, so for n>0, t(n)<5 i.e. c=5 and n0=0. However, unlike O(n) or O(n^2), I'm not sure how to formally prove this.

1

There are 1 best solutions below

2
On BEST ANSWER

Observe \begin{align} \left|n-\sqrt{n^2-10n}\right| \leq \frac{10n}{n+\sqrt{n^2-10n}} \leq 10 \end{align} for all $n$.