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

Question

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]

Answer 1

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)$.