Time complexity and summation

Question

For the following algorithm:

n=3;                          1
m=2;                          2
func(int n, int m)            3
{
    for(int i=1; i<=m; i++)   4
    {
        if(n>1)               5
        {
             func(n-1,m);     6
        }
    }   
}

I have this solution here:

$T(n,m)=mT(n-1,m)+mc$

But I don't understand steps to the final expression. Can someone describe a more detailed solution and also it is there any possibility to convert this expression to summation since it is easy for me to solve them.

Answer 1

Yves has shown you that $$T(1,m) = mc = mc\sum_{i=0}^0m^i$$ $$T(2,m) = m^2c+mc = mc(m+1) = mc\sum_{i=0}^1m^i$$ $$T(3,m) = m^3c + m^2c + mc = mc(m^2 + m + 1) = mc\sum_{i=0}^2m^i$$ From that, you can figure out that $$T(n,m) = mc\sum_{i=0}^{n-1}m^i$$ which you can prove by induction. After getting this form for $T(n,m)$, you realize that the sum is a geometric series and may be written: $$T(n,m) = mc\frac{1-m^n}{1-m}$$