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:


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

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


and finally

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

  • $\begingroup$ I would ask you to collaborate a bit your answer and also if you can to express it in summation? $\endgroup$ – J. Doe Feb 22 '18 at 19:52
  • $\begingroup$ What don't you understand, precisely ? $\endgroup$ – Yves Daoust Feb 22 '18 at 20:02
  • $\begingroup$ 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. $\endgroup$ – J. Doe Feb 22 '18 at 20:06
  • $\begingroup$ @J.Doe: I have refined the solution. $\endgroup$ – Yves Daoust Feb 22 '18 at 20:32
  • $\begingroup$ OK, what about the count variable I still don't get the right number i.e $T(3,3)$ $\endgroup$ – J. Doe Feb 22 '18 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.