1
$\begingroup$

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]
$\endgroup$
1
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.