T(n) = T(n-1) + T(n-1) vs T(n) = 2*T(n-1)

Question

If I have 2 version of code

1.)

def T(n):
    if n == 0:
        return 1
    return T(n-1)+T(n-1)

2.)

 def T(n):
    if n == 0:
        return 1
    return 2 * T(n-1)

Is my understanding correct that the time complexity of the first function is O(2^n) and the second function is O(n)

Answer 1

Yes, the running time of the first is $\Theta(2^n)$ unless you have tail-call optimization or you do memoization.

The running time of the second is $\Theta(n)$.

Beware that the input size is actually $\log_2 n$ which would make the latter function actually run in time $O(2^{\left| x \right|})$ where $x$ is the size of the input.