# How to calculate the basic steps in Fibonacci sequences to get nFn and n^2

I am reading Algorithms by Sanjoy Dasgupta, Umesh Vazirani, Christos Papadimitriou and I am trying to understand how the number of steps $$nF_n$$ and $$n^2$$ were calculated. Here's the part of the book in Chapter 0 that mentions them. Functions fib1 and fib2 are written below the excerpt.

fib1, which performs about $$F_n$$ additions, actually uses a number of basic steps roughly proportional to $$nF_n$$. Likewise, the number of steps taken by fib2 is proportional to $$n^2$$, still polynomial in $$n$$ and therefore exponentially superior to fib1.

function fib1(n)
if n = 0: return 0
if n = 1: return 1
return fib1(n - 1) + fib1(n - 2)

function fib2(n)
if n = 0 return 0
create an array f[0 ... n]
f[0] = 0, f[1] = 1
for i = 2 ... n:
f[i] = f[i - 1] + f[i - 2]
return f[n]

• – D.W.
Jan 17, 2021 at 21:33

## 1 Answer

Let's start with the second function, fib2. If you count the number of operations, then you get only $$O(n)$$. So why is the running time given as $$\Theta(n^2)$$? The reason is that the Fibonacci numbers grow exponentially, and so addition can no longer be considered an $$O(1)$$ operation. The $$n$$-th Fibonacci number is $$\Theta(n)$$ bits in length, and this leads to a running time proportional to $$\sum_{i=2}^n i = \Theta(n^2)$$.

As for fib1, we can easily write a recurrence for the running time $$T(n)$$: $$T(n) = \begin{cases} O(1) & \text{if } n \leq 1, \\ T(n-1) + T(n-2) + \Theta(n) & \text{if } n \geq 2. \end{cases}$$ For the sake of asymptotic analysis, we can replace $$\Theta(n)$$ with $$n$$ and consider $$S(n) = T(n)/n$$, which follows the recurrence $$S(n) = \begin{cases} O(1) & \text{if } n \leq 2, \\ S(n-1) + S(n-2) + 1 & \text{if } n \geq 3. \end{cases}$$ Thus $$R(n) = S(n) + 1$$ satisfies $$R(n) = R(n-1) + R(n-2)$$. Choosing appropriate initial values (which is fine, for the sake of asymptotic analysis), we find out that $$R(n) = F_n$$, and so $$T(n) = nS(n) = n(R(n) - 1) = \Theta(nF_n)$$.