2
$\begingroup$

I'm looking to work out the big-O notation for the following:

$$\frac{n^{s + 1} - 1}{n - 1} - 1$$

I have a feeling the result is $O\left( n^s \right)$ but I'm not sure how to prove it.

Any help greatly appreciated! :)

$\endgroup$
  • $\begingroup$ This question does not fit the scope of cstheory, but would certainly be welcome on math.SE. How about computing the limit for $n\rightarrow\infty$? $\endgroup$ – Anthony Labarre Oct 19 '12 at 7:43
  • $\begingroup$ @AnthonyLabarre thanks for the quick response - should it be migrated? Or should I delete and repost? $\endgroup$ – mdjnewman Oct 19 '12 at 7:51
  • $\begingroup$ I flagged it as off-topic, I suppose one of the moderators will eventually either close it or migrate it. I'd just wait and see what they decide before taking action. $\endgroup$ – Anthony Labarre Oct 19 '12 at 7:53
  • $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. I am migrating your question to Computer Science which has a broader scope. $\endgroup$ – Kaveh Oct 19 '12 at 19:26
7
$\begingroup$

Some of modifications of O described in Concrete Mathematics: Foundation for Computer Science says:

$ \qquad O(f(n)) + O(g(n)) = O(\mid f(n)\mid + \mid g(n) \mid) \qquad (9.22)\\ \qquad O(f(n))O(g(n)) = O(f(n)g(n)) \qquad \qquad \qquad (9.26) $

And using some basic knowledge of O notation and functions:

$ \qquad O(f(n) +c) = O(f(n)) \\ \qquad \forall_{n\in \mathbf N} \forall_{k>0} n^k > 0 $

Use those transformation you can came up with something like this:

$$\frac{n^{s+1}-1}{n-1}-1 = O\left(\frac{n^{s+1}-1}{n-1}-1\right) = O\left(\frac{n^{s+1}-1}{n-1}\right) = O\left(\frac{1}{n-1}\right)O\left(n^{s+1}-1\right) = $$ $$ O\left(\frac{1}{n}\right)O\left(n^{s+1}\right) = O\left(\frac{n^{s+1}}{n}\right) = O(n^s) $$

So your intuition was right.

$\endgroup$
  • $\begingroup$ The book you mentioned seems like a great reference, thanks! $\endgroup$ – mdjnewman Oct 19 '12 at 23:57

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.