How to calculate the basic steps in Fibonacci sequences to get nFn and n^2
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) &amp; \text{if } n \leq 1, \\
T(n-1) + T(n-2) + \Theta(n) &amp; \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) &amp; \text{if } n \leq 2, \\
S(n-1) + S(n-2) + 1 &amp; \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)$.