# Proving big oh for a function

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.

• Big $O$ is not THE upper bound, it's ANY bound, so if a $k$ works in your case, then any higher $k$ will also work. More formally: en.wikipedia.org/wiki/Big_O_notation#Formal_definition – Stop hurting Monica Nov 7 '14 at 23:12
• Indeed -- Jean-Claude is completely right. What your prof said really makes no sense to me, if you've reported it accurately. – John Hughes Nov 7 '14 at 23:14
• Sorry, let me clarify. His words were that the left-hand side grows no faster than the right-hand side. Is my proof correct? – mylasthope Nov 7 '14 at 23:15
• Notice that $n^2-1<n^2$, hence $\sqrt{n^2-1}<n$, and the smallest possible $k$ is $1$. – Stop hurting Monica Nov 7 '14 at 23:17
• Thank you! That makes a lot more sense than what I was doing. Also, when I'm working on these, I'm supposed to make the right-hand side bigger with each step, correct--which is why going from -1 to -n is incorrect? – mylasthope Nov 7 '14 at 23:19

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.