My instructor claims this is $O(n)$, but shouldn't it be $O(n^{1.5})$? If we ignore the $+1$ and $-1$ then this is just $O(n^{1.5})$. Is this reasoning right?
Any help is appreciated.
Asked
Active
Viewed 197 times
8
-
What is the specific note from your instructor? As you've written it what you've said is correct (technically it's the fact that it's in $\Theta(n^{1.5})$ that you likely care about, since for instance it's also correct to say that your expression is in $O(n^{1000})$), but I suspect some misunderstanding somewhere along the way. – Steven Stadnicki Jun 26 '17 at 18:54
-
@Steven It is a question from a practice exam, and O(n) was the official solution from the instructor. – XKCD Jun 26 '17 at 18:55
-
2@XKCD Unless there is some other context to this, your instructor is simply wrong. – balddraz Jun 26 '17 at 19:07
2 Answers
8
Yes, $O((n+1)\sqrt{n-1}) = O(n^{3/2})$.
It should be noted that technically $(n+1)\sqrt{n-1}$ is Big Oh of any function that grows at least as fast as $n^{3/2}$. Thus $(n+1)\sqrt{n-1}$ is $O(n^{1000})$ but not $O(n)$. However, I've seen some CS people use Big Oh notation as if it were Big Theta.
Bob Krueger
- 6,226
2
More strongly, $(n + 1)\sqrt{n - 1} \sim n\sqrt{n};$ to wit, the limit of the ratio is 1.
ncmathsadist
- 49,383