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) = 0, f(1) = 1 for i = 2 ... n: f(i) = f(i + 1) + f(i + 2) return f(n)