Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am watching the Introduction to algorithm video, and the professor talks about finding a Fibonacci number in $\Theta(n)$ time at point 23.30 mins in the video.

  1. How is it $\Theta(n)$ time?

  2. Which case of the master theorem does it fall under?

  3. What would the recursion tree look like if we try to use a divide and conquer approach?

P.S: I know pretty much what the $\Theta(n)$ notation means, so please write your answer accordingly.

share|cite|improve this question
Do you mean $\Theta(n)$? I've never heard of small-theta time. – Kevin Carlson Aug 3 '12 at 12:21
yes exactly . small theta time has no meaning since Θ gives a tight bound. I will edit . – Geek Aug 3 '12 at 12:22
In question (3), do you mean the algorithm he discussed earlier where he computed $fib(n)$ recursively using $fib(n) = fib(n-1)+fib(n-2)$? If you do, I'll add a sample picture to my answer. – Rick Decker Aug 3 '12 at 13:41
See my latest edit to see how to get big-theta in LaTeX. – Rick Decker Aug 3 '12 at 13:50
It seems, to get $T(n) = \Theta(n)$, you'll have to use memoization or better yet just pass on the previous calculations to the next recursive call. Otherwise, the recursion tree will get exponentially big. See here for a look at the repeated calculations for fib(5). – ladaghini Aug 3 '12 at 14:28

3 Answers 3

up vote 4 down vote accepted

What he's doing is using a simple example of what's known as dynamic programming, where one computes a function $f(n)$ by working up from the bottom to get to the desired result. Specifically, to compute $fib(n)$, the $n$-th Fibonacci number, he's doing this

   if (n <= 1)
      return n
      old = 0, prior = 1, next
      for i = 2 to n
         next = old + prior
         old = prior
         prior = next
      return next

To see this in action, we compute $fib(4)$, which we know is $3$:

i  old  prior  next
2   0     1      1    (compute next = old + prior)
2   1     1      1    (shift everything to the left)
3   1     1      2    (compute next again)
3   1     2      2    (shift again)
4   1     2      3    (and so on...)
4   2     3      3

How long does this algorithm take? No need for the Master Theorem here: we have an algorithm that consists, essentially, of a loop, so assuming you can add in constant time, this will have running time $T(n) = \Theta(n)$.

(Actually, this won't work at all on real machines, since $fib(n)$ grows so fast that the numbers will quickly exceed the size of an integer. For example, $fib(2500)$ is 523 decimal digits long, so we'd need to implement some big integer package to do the addition and assignment statements, increasing the run time of this algorithm.)

The recursion tree for the original (terrible) recursive algorithm looks like this, when computing $fib(4)$:

enter image description here

For example, the first call, to $fib(4)$, requires two recursive calls, to $fib(3)\text{ and }fib(2)$. Notice how inefficient this is: just to compute $fib(4)$ we needed nine function calls. In fact, this is a classic example of when not to use recursion, especially since there are vastly more efficient ways to do this porblem.

share|cite|improve this answer

I have to say I know very little about algorithms, but for your second question I did a quick search to see if that theorem even applies to the Fibonacci sequence.

According to this link:

  • Master Theorem does NOT apply to Factorial or recursive Fibonacci, because their runtimes do not satisfy the appropriate type of recurrence.

(Added later, after the link died)

Here is the relevant snippet from the link, which was a set of notes in a computer science course. It can be seen with this Wayback link

Since then, it looks like the notes have been relocated to this location and are more grammatical now. I think the new version of what I was citing starts around page 81 of these notes. It's a little disturbing though that I can't find "Master theorem" referenced by name via a simple text search.

share|cite|improve this answer
thats okay . I was also thinking about the same but wasn't sure . But how Θ(n) ? – Geek Aug 3 '12 at 12:26
Your link is dead. Could you update it, please? – Maksim Dmitriev Jun 17 at 20:47
@MaksimDmitriev Done. – rschwieb Jun 18 at 13:55
@Geek, Not Found. The requested URL /~fpitt/20079/CSC236/lectures/LN06.txt was not found on this server. – Maksim Dmitriev Jun 19 at 8:47
@MaksimDmitriev I had hoped you would read the post and click either of the fixed links, but I guess I didn't bother moving the original link. I did this also, and now you can't go wrong. Regards. – rschwieb Jun 19 at 10:12

Sorry. I would put this as a comment, but I don't have enough rep points for that yet. Anyways, your solution to the third question?


It seems to be divide and conquer because it splits n by 2 every time.

The link I provided you answers the first question too actually.


T(n) = 2n-1 ~ O(n)

share|cite|improve this answer
There's a very clear exposition of this method in a long-out-of-print book. I'd cite it, but modesty forbids. – Rick Decker Aug 3 '12 at 13:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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