0
$\begingroup$

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

The answer choices I selected:

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.