StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You model the time function to calculate <code>Fib(n)</code> as sum of time to calculate <code>Fib(n-1)</code> plus the time to calculate <code>Fib(n-2)</code> plus the time to add them together (<code>O(1)</code>).</p> <p><code>T(n<=1) = O(1)</code></p> <p><code>T(n) = T(n-1) + T(n-2) + O(1)</code></p> <p>You solve this recurrence relation (using generating functions, for instance) and you'll end up with the answer.</p> <p>Alternatively, you can draw the recursion tree, which will have depth <code>n</code> and intuitively figure out that this function is asymptotically <code>O(2</code><sup><code>n</code></sup><code>)</code>. You can then prove your conjecture by induction.</p> <p>Base: <code>n = 1</code> is obvious</p> <p>Assume <code>T(n-1) = O(2</code><sup><code>n-1</code></sup><code>)</code>, <i>therefore</i> </p> <p><code>T(n) = T(n-1) + T(n-2) + O(1)</code> <i>which is equal to</i></p> <p><code>T(n) = O(2</code><sup><code>n-1</code></sup><code>) + O(2</code><sup><code>n-2</code></sup><code>) + O(1) = O(2</code><sup><code>n</code></sup><code>)</code></p> <p>However, as noted in a comment, this is not the tight bound. An interesting fact about this function is that the T(n) is asymptotically <b>the same</b> as the value of <code>Fib(n)</code> since both are defined as </p> <p><code>f(n) = f(n-1) + f(n-2)</code>. </p> <p>The leaves of the recursion tree will always return 1. The value of <code>Fib(n)</code> is sum of all values returned by the leaves in the recursion tree which is equal to the count of leaves. Since each leaf will take O(1) to compute, <code>T(n)</code> is equal to <code>Fib(n) x O(1)</code>. Consequently, the tight bound for this function is the Fibonacci sequence itself (~<code>θ(1.6</code><sup><code>n</code></sup><code>)</code>). You can find out this tight bound by using generating functions as I'd mentioned above.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload