Explanation to time complexity of Fib(n)

Question

I very well know that recursive Fib(n) has time complexity of O(2^n). I am also able to come to that result by solving the following

T(n) = T(n-1)+T(n-2).

But when I take an example I get stuck. For eg: n=4 acc to recursive solution

T(1) = u #some constant 
and, T(2) = u #some constant
Now, T(4) = T(3)+T(2)
          = T(2)+T(1)+u
          = u+u+u 
          = 3u

I was expecting the result to be 16u.

Check this answer https://stackoverflow.com/a/360773/7629560 — samthegolden, Apr 22 '20 at 08:30
Does this answer your question? [Computational complexity of Fibonacci Sequence](https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence) — Paul Hankin, Apr 22 '20 at 08:53
@PaulHankin I had read that answer and understood the calculations as well, but got stuck when I tried those calculations with a particular example as I have mentioned above. — Roseau, Apr 22 '20 at 09:09

xenteros · Accepted Answer · 2020-04-22T12:30:52.000

3

The Big-O notation is related to the asymptotic complexity, so we are interested in how the complexity grows for big numbers.

Big-O refers actually to an upper limit for the growth of a function. Formally, O(g) is a set of functions that are growing not faster than k*g.

Let me give you a few examples of functions that are in O(2^n):

The fact that T(n) in O(2^n) doesn't mean, that the number of operations will be exactly 2^n.

It only means, that the limit of the supremum of a sequence |T(n)/(2^n)| as n -> inf is finite.

edited Apr 22 '20 at 12:30

answered Apr 22 '20 at 08:28

xenteros

But if it's negative infinity then the complexity is not optimal :) – samthegolden Apr 22 '20 at 08:32
@samthegolden oh yea! – xenteros Apr 22 '20 at 08:35
The definition is wrong; the "limit" form of the definition of big O is that lim sup |f/g| is finite as n -> inf. The lim sup is necessary because often the limit doesn't exist. The absolute value in the definition prevents any idea of minus infinity coming in. – Paul Hankin Apr 22 '20 at 08:53
I can see you've edited it, but you still have a wrong definition. T(n) in O(2^n) means that lim sup |T/2^n| is finite. It doesn't mean that the limit of |T/2^n| exists (although it does in this case because 2^n grows exponentially faster than T, and the limit is zero). – Paul Hankin Apr 22 '20 at 09:35
You've edited it again, but it's still wrong. It's the lim sup that is finite, not the limit. They're not the same thing. Here's wikipedia's definition: https://en.wikipedia.org/wiki/Big_O_notation#Formal_definition – Paul Hankin Apr 22 '20 at 10:47
@PaulHankin now it should be fine – xenteros Apr 22 '20 at 12:31

1 Answers1