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
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
fib2is 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, f = 1 for i = 2 ... n: f[i] = f[i - 1] + f[i - 2] return f[n]