0
$\begingroup$

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.

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

1 Answer 1

0
$\begingroup$

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

$\endgroup$
9
  • $\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, 2018 at 19:52
  • $\begingroup$ What don't you understand, precisely ? $\endgroup$
    – user65203
    Feb 22, 2018 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, 2018 at 20:06
  • $\begingroup$ @J.Doe: I have refined the solution. $\endgroup$
    – user65203
    Feb 22, 2018 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, 2018 at 20:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .