13
$\begingroup$

Using the following recursive Fibonacci algorithm:

def fib(n):
   if n==0:
      return 0
   elif n==1
      return 1
   return (fib(n-1)+fib(n-2))

If I input the number 5 to find fib(5), I know this will output 5 but how do I examine the complexity of this algorithm? How do I calculate the steps involved?

$\endgroup$
23
$\begingroup$

Most of the times, you can represent the recursive algorithms using recursive equations. In this case the recursive equation for this algorithm is $T(n) = T(n-1) + T(n-2) + \Theta(1)$. Then you can find the closed form of the equation using the substitution method or the expansion method (or any other method used to solve recurrences). In this case you get $T(n) = \Theta(\phi^n)$, where $\phi$ is the golden ratio ($\phi = \frac{(1 + \sqrt{5})}{2}$).

If you want to find out more about how to solve recurrences I strongly recommend you to read chapter 4 of Introduction to Algorithms.

$\endgroup$
0
$\begingroup$

as an alternative to recurrence relations/ math analysis (but not a substitute) a simple empirical exercise, apparently not taught very often in classes but very informative, is to count the # of executions of the function, and then graph the count for a range of small n inputs, and then curve fit the result. results will generally closely match the theoretical math approach.

good supporting material for this exercise can be found in the free online chapter 3, running time of algorithms/ Foundations of Computer Science, Ullman

$\endgroup$
  • $\begingroup$ 1) Plotting does in no way replace formal analysis. It's easily fooled. 2) I think you are misrepresenting the source you quote. They do mention plotting, but not as a way to determine "complexity". 3) FWIW, I do disagree with the approach and it's use as Ullman presents it, but that's not your fault. $\endgroup$ – Raphael Aug 13 '16 at 16:09
  • 1
    $\begingroup$ the answer starts with essentially your disclaimer, saying plotting is not a substitute for math analysis. plotting is a scientific method and to say/ observe it is sometimes fooled is to learn about/ evoke statistical aspects of data, which is another foremost aspect of scientific analysis. think to say it is "easily fooled" is rather dramatic, there are "pathological" cases where it fails but they are typically "contrived"... the question was to examine the complexity of the algorithm and empirical analysis is a key aspect/ angle on that, and obviously not the sole angle etc... $\endgroup$ – vzn Aug 13 '16 at 16:56
0
$\begingroup$

The result of fib (n) is the sum of all recursive calls that returned 1. Therefore there are exactly fib (n) recursive calls evaluating fib (1). So the execution time is Ω(fib (n)); you'd need to show that the calls returning 0 and the other recursive calls don't add significantly to this.

The same reasoning would apply to any recursively defined function that either returns 1, or 0, or the result of another recursive call.

$\endgroup$
  • $\begingroup$ "at least O (fib (n))" -- that does not make any sense. You want to use $\Omega$. $\endgroup$ – Raphael Aug 15 '16 at 19:01
  • $\begingroup$ Feel free to edit the answer if you feel strongly about it. $\endgroup$ – gnasher729 Aug 17 '16 at 14:44
0
$\begingroup$

A lower bound is intuitive: $T(n)=T(n-1)+T(n-2)$ $T(n)>2T(n-2)$ since $T(n-1)>T(n-2)$ Hence $T(n)= \Omega(c^{n})$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.