0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Stop hurting Monica Nov 7 '14 at 23:12
  • $\begingroup$ Indeed -- Jean-Claude is completely right. What your prof said really makes no sense to me, if you've reported it accurately. $\endgroup$ – John Hughes Nov 7 '14 at 23:14
  • $\begingroup$ Sorry, let me clarify. His words were that the left-hand side grows no faster than the right-hand side. Is my proof correct? $\endgroup$ – mylasthope Nov 7 '14 at 23:15
  • 1
    $\begingroup$ Notice that $n^2-1<n^2$, hence $\sqrt{n^2-1}<n$, and the smallest possible $k$ is $1$. $\endgroup$ – Stop hurting Monica Nov 7 '14 at 23:17
  • $\begingroup$ 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? $\endgroup$ – mylasthope Nov 7 '14 at 23:19
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ He said that we don't have to find the smallest k. "you do not need to prove your k is the smallest possible, but you do need to find C and k and prove that they work." So, I said k is 2. I hope that's fine. $\endgroup$ – mylasthope Nov 7 '14 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.