Understanding $O(2^n)$ time complexity due to recursive functions Consider the following binary recursive fibonassi program:

Algorithm binaryFib(k)  //k is assumed to be non-negative integer
   if (k &lt;= 1)
      return k
   else
      return binaryFib(k-1) + binaryFib(k-2)
end binaryFib


The recurrence relation for above is:

$T(n) = T(n-1) + T(n-2)$

The run time complexity for the same is $O(2^n)$, as can be seen in below pic for $n=8$:



However if you look at the bottom of the tree, say by taking $n=3$, it wont run $2^n$ times at each level: 



Q1. Wont this fact have any effect on time complexity or does the time complexity $O(2^n)$ ignores this fact?

Q2. I guess I can rephrase Q1 by eliminating above fact with following recurrence relation: $T(n) = 2 T(n-1)$. Does this recurrence relation still have same $O(2^n)$ time complexity?

Q3. Finally I want to generalize: Does the recurrence relation $T(n)=k\times T(n-1)$ have $O(k^n)$ time complexity?
If you look at the code, it is quite obvious that there are exactly fib(N) - 1 additions. Therefore the time complexity is $\Theta(fib(n))$.