[Solved]: If recursive Fibonacci is $O(2^N)$ then why do I get 15 calls for N=5?

I have an $O(2^n)$ runtime, why do I not observe $2^n$ recursive calls for $n=15$?

There are many things wrong in the implied conclusion.

1. $O(_)$ only gives you an upper bound. The true behaviour may be of much smaller growth.
2. Asymptotics (like $O(_))$ only give you only something in the limit, that is you can only expect the bound to hold for large $n$.
3. Since you use $O$ as though it was $Omega$, note that a (lower) bound on runtime does not necessarily translate into a (lower) bound on recursive calls, each of which may take $omega(1)$ time. Similarly, a tight upper runtime bound (which you don’t have) may not be a tight upper bound on the number of recursive calls for the same reasons.

You can analyse exactly how many recursive calls you need. Just solve the recurrence $qquaddisplaystyle begin{align*} f(0) &= 1, f(1) &= 1, f(n) &= f(n-1) + f(n-2) + 1, quad n geq 3, end{align*}$ which adds up $1$ for every recursive call your program makes. See here for more detail on how you get to such recurrences. See here how to do that, or use computer algebra. The result is $qquad f(n) = 2F_{n+1} – 1$; insert $n=5$ and you will get $f(n) = 15$. It’s not that surprising that the Fibonacci numbers $F_n$ should show up. Inserting their known closed form, we get $qquaddisplaystyle f(n) = frac{2}{sqrt{5}} cdot Bigl( varphi^{n+1} – (1-varphi)^{n+1} Bigr) – 1$ with $varphi = frac{1 + sqrt{5}}{2} approx 1.62$ the golden ratio. This closed form of $f(n)$ implies $qquaddisplaystyle f(n) sim frac{2}{sqrt{5}} cdot varphi^{n+1} approx 1.45 cdot 1.62^n$ since $0< 1 – varphi < 1 < varphi$. We see that the $O(2^n)$-bound is rather loose — it has exponential absolute and relative error.