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