# Recursion with loop inside

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.

• Possible duplicate of Is there a system behind the magic of algorithm analysis? – David Richerby Feb 22 '18 at 10:37
• @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. – J. Doe Feb 22 '18 at 10:49
• 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. – David Richerby Feb 22 '18 at 11:12
• @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. – J. Doe Feb 22 '18 at 11:31
• 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. – David Richerby Feb 22 '18 at 12:25