Time and Space Complexity Trouble
<p>I've seen so many time complexity problems but none seem to aid in my understanding of it - like really get it.</p>

<p>What I have taken from my readings and attempts at practices all seems to come down to what was mentioned here <a href="http://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation">Determining complexity for recursive functions (Big O notation)</a> in the answer coder gave - which in fact did help me understand a little more about what's going on for time complexity.</p>

<p>What about a function that such as this:</p>

<pre><code>def f(n):
if n &lt; 3:
    return n
if n &gt;= 3:
    return f(n-1) + 2*f(n-2) + 3*f(n-3)
</code></pre>

<p>Since the function calls the function 3 times, does that mean that the time complexity is O(3^n)?</p>

<p>As for the space complexity, it seems to be linear hence I propose the complexity to be O(n).</p>

<p>Am I wrong about this?</p>

<blockquote>
  <p>Since the function calls the function 3 times</p>
</blockquote>

<p>This isn't really correct, but rather lets use examples that are more exact that your ad-hoc example.</p>

<pre><code>def constant(n):
    return n*12301230
</code></pre>

<p>This will always run in the same amount of time and is therefore O(1)</p>

<pre><code>def linear(n):
    total = 0
    for x in xrange(n):
        total+=1
    return total
</code></pre>

<p>This has O(N) time </p>

<pre><code>def quadratic(n):
    total = 0
    for x in xrange(n):
        for y in xrange(n):
             total+=1
    return total
</code></pre>

<p>This runs in quadratic time O(N^2) since the inner loop runs n times and the outer loop runs n times.</p>

<p>There are also more specific examples for log(N), N*log(N), (2^N), etc but, going back to your question:</p>

<blockquote>
  <blockquote>
    <p>Since the function calls the function 3 times, does that mean that the time complexity is O(3^n)?</p>
  </blockquote>
</blockquote>

<p>If the function is called 3 times, it will still be constant time for <code>constant(x)</code>, linear for <code>linear(x)</code> and quadratic for <code>quadratic(x)</code>. Importantly, O(3^n) is exponential time and is not the same as n^3. Then, we would not use a 3 as the base but a 2^n as a standard.</p>

<p>So your function will have a constant time for x&lt;3. Best approximation to what your function gives, I'd run it through a timer but its recursive and difficult to compute. If you provide another, non-recursive example I'll be happy to tell you its complexity.</p>

<p>Hope this helps a bit, the graph doesn't do justice to how much faster 2^n grows in comparison to n^2 but it's a good start.</p>

<p><a href="http://i.stack.imgur.com/sCiCp.png" rel="nofollow"><img src="http://i.stack.imgur.com/sCiCp.png" alt="Time complexity"></a></p>

python recursion time-complexity