0
$\begingroup$

What is the time complexity of this algorithm? I assume that is $O(3^n)$

n=3
recLoop(int n)
{
    for(int i=0; i<3; i++)
    {
        if(n>0)
        {
             recLoop(n-1); 
        }
        count++;
    }   
}

n 0 1 2 3 4


count 3 9 27 81 243

From this, I get $O(3^{n+1})$

If I change my algorithm to:

recLoop(int n)
{
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<2; j++)
        {
            count++;
        }
    }
    for(int i=0; i<3; i++)
    {
        if(n>0)
        {
            recLoop(n-1);
        }
        else
            count++;
    }
}

From first nested loops $O(nm)$ so what is the total complexity of this algorithm?


n 0 1 2 3 4


count 9 33 105 321 969

The possible solution is a bit hard for me to understand and to translate my problem. I need a bit more description of my problem.

$\endgroup$
  • 1
    $\begingroup$ Possible duplicate of Is there a system behind the magic of algorithm analysis? $\endgroup$ – David Richerby Feb 22 '18 at 10:37
  • $\begingroup$ @DavidRicherby it is a bit hard for me to translate my algorithm into a mathematical expression. If you think that that answer can solve my problem can you please explain to me how I can solve mine. $\endgroup$ – J. Doe Feb 22 '18 at 10:49
  • 1
    $\begingroup$ Let $T(n)$ be the cost of running recloop(n), expresss that in terms of $T(n-1), \dots, T(0)$ and attempt to solve the recurrence. $\endgroup$ – David Richerby Feb 22 '18 at 11:12
  • $\begingroup$ @DavidRicherby For the recloop(n) I know the $T(n) = nc$, but adding the for loop before the recurrence I don't know how to solve it. $\endgroup$ – J. Doe Feb 22 '18 at 11:31
  • $\begingroup$ The question I linked to explains how to write the recurrence in terms of what the code is doing. $T(n)=nc$ isn't a recurrence: it's a statement thatrecloop(n) takes time linear in $n$, which doesn't take into account the recursive calls. $\endgroup$ – David Richerby Feb 22 '18 at 12:25

Your Answer

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

Browse other questions tagged or ask your own question.