Big O Notation for a complexity analyses

Question

I have an algorithm which for two input parameters $m,n$ has a complexity of:

$$\sum_{i=1}^n m^n$$

this gives me the closed form of geometric series:

$$\frac{m(m^n-1)}{m-1}$$

Is it correct if I write that my algorithm has a complexity of $O(\frac{m(m^n-1)}{m-1})$, or could this be further simplified?

Note that $m \geq 1, n \geq 1$.

Answer 1

$\frac{m(m^n-1)}{m-1} \leq 2(m^n-1)$ for sufficiently large $m$, since $\lim_{m \to \infty} \frac{m}{m-1}=1$ implies that there are only finitely many terms greater than $2$.

Hence, we can just write

$\frac{m(m^n-1)}{m-1}=O(m^n-1)=O(m^n)$.

In the case that $m=1$, the sum is just $1+...+1=n$.

Answer 2

If you know the exact expression

$$\frac{m(m^n-1)}{m-1}$$ you can just keep it like it is.

Or, after dropping the two neglectible $-1$s,

$$\frac{m(m^n-1)}{m-1}=O(m^n).$$

As pointed by others, the expression reduces to $n$ when $m=1$. You can account for this by the notation

$$O(m^n+n).$$

Answer 3

For any $m,n\geq 1$, we have $\sum_{i=1}^n m^n = n \cdot m^n$. Note that there is no $i$ in any term of the sum.