[Solved]: Finding big O notation of function with two parameters

Problem Detail: 

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

Asked By : mdjnewman

Answered By : Bartosz Przybylski

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6176