# Finding big O notation of function with two parameters

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! :)

• 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$? – Anthony Labarre Oct 19 '12 at 7:43
• @AnthonyLabarre thanks for the quick response - should it be migrated? Or should I delete and repost? – mdjnewman Oct 19 '12 at 7:51
• 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. – Anthony Labarre Oct 19 '12 at 7:53
• 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. – Kaveh Oct 19 '12 at 19:26

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)$$