What is time complexity of my algorithm

Question

I have this 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
        }
    }   
}

How can I find the time complexity of this one? I know that for the for loop I can write:

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

But I don't know how can I write the recursion in this loop.

Answer 1

The running time follows the recurrence

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

($c$ accounts for one execution of the loop and the if.)

Then applying the recurrence several times

$$T(1,m)=mc,\\T(2,m)=m^2c+mc,\\T(3,m)=m^3c+m^2c+mc,\\\cdots$$

and finally

$$T(n,m)=\frac{m^n-1}{m-1}mc$$ which is of order $O(m^n)$.