Find a $C$ and $k$ such that $\sqrt{n^2 - 1}$ = $O(n^k)$. My professor has stated that there are two different $k$'s. One from the problem statement and one from the definition of big-oh. I know that big oh is the upper bound, so I need to get the left-hand side to be smaller or equal to the right-hand side. Is the following correct?
$\sqrt{n^2 - 1} \le (\sqrt{n^2 - 1})^{2}$
$\to \sqrt{n^2 - 1} \le n^2 - 1$
$\to \sqrt{n^2 - 1} \le n^2 - n$
$\to \sqrt{n^2 - 1} \le n(n - 1)$
Thus, $k$ = 2, $C$ = 1 and $n$ has to be $\ge 2$.
I'm not quite sure how to remove the $- 1$. In class, we dealt with addition rather than subtraction.
An answer suitable for your professor (if you the statement is correctly given): these numbers are $e$ and $\pi$.
And clarificiation for you. As $\sqrt{n^2-1}<n $, every $n^k$, where $k\geq1$, is a correct bound.