# What is time complexity of my algorithm

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.

• How is recLoop defined? – VHarisop Feb 22 '18 at 19:20
• @VHarisop I fixed it. – J. Doe Feb 22 '18 at 19:21
• func seems to accept two arguments, but you only pass it one recursively – Dan Uznanski Feb 22 '18 at 19:21
• @DanUznanski Sorry copy-paste stuff. I think now it's correct! – J. Doe Feb 22 '18 at 19:22

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

• I would ask you to collaborate a bit your answer and also if you can to express it in summation? – J. Doe Feb 22 '18 at 19:52
• What don't you understand, precisely ? – Yves Daoust Feb 22 '18 at 20:02
• Two things: 1) Why $T(1,m) = cm$ ? and 2) If the solution is $cm^n$ than for $n=3$ and $m=3$ it is $T(3,3) = 27$, but If I add a count++ before line 6 I'm getting 39 and not 27. – J. Doe Feb 22 '18 at 20:06
• @J.Doe: I have refined the solution. – Yves Daoust Feb 22 '18 at 20:32
• OK, what about the count variable I still don't get the right number i.e $T(3,3)$ – J. Doe Feb 22 '18 at 20:40