Orders of growth involving both recursion and two inner for loops
<p>I have attempted the below question but I am uncertain whether I am correct or not. I have arrived at the conclusion that it is a big theta of n^2 function. My reasoning is that the inner 2 loops for i and for j will amount to a sequence of operations, 0, 1, 2, 3, 4, 5....x -1, which can be translated into (x * x - 1) /2 by the arithmetic operation. However, the outer recursive call kind of trips me up. I am tempted to look at the outer recursive call as yet another while loop but I fought it off because it isn't exactly another while loop or for loop because x also changes. Can someone help me arrive at a better understanding of the below question? </p>

<pre><code>    def foo(x):
        if x &lt; 1: 
            return 'boo'
        for i in range(x): 
            for j in range(i):
                return foo(i + j)
        return foo(x-1)
</code></pre>

<p>REVISION: I just ran this code through my python interpreter and turns out it will be constant time as it is a trick question. The reason being, the return statement will just evaluate to foo(1), and then 'boo' gets outputted no matter what size of n you are at. </p>

<p>But----> What if I were to change my code to the following. Is the run time now theta(n^2) or theta(n^3)? </p>

<pre><code>    def foo(x):
        if x &lt; 1: 
            return 'boo'
        for i in range(x): 
            for j in range(i):
                print(i + j)
        return foo(x-1) 
</code></pre>

<p><strong>EDIT:</strong> First there was <code>i+i</code> in question but now there is <code>i+j</code> so now my answer is wrong.</p>

<hr>

<p>When <code>x &lt; 1</code> it prints 'boo' - nothing intersting.</p>

<p>When <code>x &gt;= 1</code> then you can reach loops</p>

<pre><code>for i in range(x): 
    for j in range(i):
        return foo(i+i)
</code></pre>

<p>so let <code>x = 1</code> and you have</p>

<pre><code>for i in range(1): 
    for j in range(i):
        return foo(i+i)
</code></pre>

<p>so let <code>i = 0</code> - and you have </p>

<pre><code>    for j in range(0):
</code></pre>

<p>and it will newer run </p>

<p>so let <code>i = 1</code> - and you have </p>

<pre><code>    for j in range(1):
</code></pre>

<p>and for <code>j = 0</code> you can run </p>

<pre><code>    return foo(2)
</code></pre>

<p>and you return to the beginnig of this description.<br>
And you will again get <code>return foo(2)</code>. Check it on your own.  </p>

<p>So for 'x >= 1' you always get <code>return foo(2)</code>.<br>
So you can reduce this code to </p>

<pre><code>def foo(x):
    if x &lt; 1: 
        return 'boo'
    return foo(2)
</code></pre>

<p>(you will never reach <code>return foo(x-1)</code>)</p>

<p>You have infinite function.</p>

<p>(I hope I'm right)</p>

python recursion runtime