# Finding the Big-O and Big-Omega bounds of a program

I am asked to select the bounding Big-O and Big-Omega functions of the following program:

void recursiveFunction(int n) {
if (n < 2) {
return;
}

recursiveFunction(n - 1);
recursiveFunction(n - 2);
}


From my understanding, this is a Fibonacci sequence, and according to this article here, https://www.geeksforgeeks.org/time-complexity-recursive-fibonacci-program/, the tight upper bound is $$1.6180^n$$. Thus, I chose all the Big-O bounds >= exp(n) and all the Big-Omega bounds <= exp(n). Below are the choices:

O(1)
O(log n)
O(n)
O(n^2)
O(exp(n))

Om(1)
Om(log n)
Om(n)
Om(n^2)
Om(exp(n))


O(n^2)
O(exp(n))

Om(1)
Om(log n)
Om(n)
Om(n^2)
Om(exp(n))


However, it was alerted that a few of my answers were incorrect (not sure which of them). This seems strange, considering that this recursive function mimics the calls of a fibonacci sequence which has a Big-Theta exponential time complexity.

$$1.6180^n$$ is not an upper bound to the running time of your program, not even up to multiplicative constants (in fact it is a lower bound). However $$O(\phi^n)$$ is a valid upper bound, where $$\phi = \frac{1+\sqrt{5}}{2} > 1.618$$ is the golden ratio. It is also easy to see that your program takes $$\Omega(\phi^n)$$ time, so the above upper bound is asymptotically tight.
That said, $$\phi^n \not\in O(n^2)$$, so that answer is incorrect. Moreover, $$\phi^n \not\in \Omega(e^n)$$ since $$\phi < e$$, so that answer is incorrect too.
Finally, notice that your answers contradict each other since you say that the running time of the program is both in $$\Omega(e^n)$$ and in $$O(n^2)$$ but $$\Omega(e^n) \cap O(n^2) = \emptyset$$.