human
I am working on the file "CS/Part_1_Complexity_RunTimeAnalysis.ipynb".
The first task is:
Whenever we have an algorithm, there are three questions we always ask about it:

Is it correct?
How much time does it take, as a function of n? 
And can we do better?

1. Correctness
For this question, the answer is yes because it is almost a line by line implementation of the definition of the Fibonacci sequence.
2. Time complexity as a function of n
Let $T(n)$ be the number of computer steps needed to compute $fib(n)$.
what can we say about this function? For starters, if $n$ is less than 2, the procedure halts almost immediately, after just a couple of steps. Therefore,
$$ T(n)≤2 \, \mbox{for} \, n≤1. $$
For larger values of $n$, there are two recursive invocations of $fib$, taking time $T (n − 1)$ and $T(n−2)$, respectively, plus three computer steps (checks on the value of $n$ and a final addition).
Therefore,
$$ T(n) = T(n−1) + T(n−2)+3\, \mbox{for} \,n>1. $$
Compare this to the recurrence relation for $F_n$, we immediately see that $T(n) ≥ F_n$.
This is very bad news: the running time of the algorithm grows as fast as the Fibonacci numbers! $T(n)$ is exponential in $n$, which implies that the algorithm is impractically slow except for very small values of $n$.
Let’s be a little more concrete about just how bad exponential time is. To compute $F_{200}$,
the $fib$ algorithm executes $T (200) ≥ F_{200} ≥ 2^{138}$ elementary computer steps. How long this actually takes depends, of course, on the computer used. At this time, the fastest computer in the world is the NEC Earth Simulator, which clocks 40 trillion steps per second. Even on this machine, $fib(200)$ would take at least $2^{92}$ seconds. This means that, if we start the computation today, it would still be going long after the sun turns into a red giant star.
Can you write Python program for it?
 Write me a Python program to compare this to the recurrence relation for $F_n$, we immediately see that $T(n) ≥ F_n$?
assistant
#Here is Python program to compare this to the recurrence relation for $F_n$, we immediately see that $T(n) ≥ F_n$.

# This function provides a way to track function calls

def count(f):
    def counted(n):
        counted.call_count += 1
        return f(n)
    counted.call_count = 0
    return counted

fib = count(fib)

t0 = time()

n = 5
fib(n)

print ('This recursive implementation of fib(', n, ') took', round(time() - t0, 4), 'secs')
print ('And {0} calls to the function'.format(fib.call_count))

t0 = time()

n = 30
fib(n)

print ('This recursive implementation of fib(', n, ') took', round(time() - t0, 4), 'secs')
print ('And {0} calls to the function'.format(fib.call_count))