4
$\begingroup$

I'm struggling to determine the correct time complexity of a recursive function from an exam question. The function definition is as follows:

fun (n) {

if (n == 1)
    return 0;
else
    return fun(n-1) + fun(n/2);

}

the options :

A. O(log2n)

B. O(√n)

C. O(n log2n)

D. O(n)

E. O(n²)

F. O(n³)

I'm sure the complexity is greater than O(n^2) because I tested it, but I think the answer is 2^n but that's not in the options

$\endgroup$
0

2 Answers 2

5
$\begingroup$

None of the answers are correct, the recursive equation

$$T(n) = 1 + T(n-1) + T(\lfloor n /2 \rfloor), \quad T(0) = 1$$

gives solution $T(n) = {}$$\text{A346912}$$(n) = 2 \cdot $$\text{A000123}$$(n) - 1$.

$\text{A000123}$$(n)$ is also the number of ways $2n$ can be partitioned into powers of two. This function has highly non-trivial asymptotics, but they are certainly not polynomial.

$\endgroup$
2
  • $\begingroup$ Thank you very much, this was helpful $\endgroup$ Commented May 4 at 22:55
  • $\begingroup$ This makes me think information is just missing from the question to be honest. Maybe the author of the question had originally intended this to be a Dynamic Programming problem, where you cache all the answers? (So just calculate all of the answers for fun(N), from N = 0 to N = n) Which would make the problem O(N), if caching is used. $\endgroup$ Commented May 6 at 1:54
3
$\begingroup$

The definition you've given for the sequence $f(n)$ is $$f(n) = \begin{cases} 0, &n = 1 \\ f(n-1) + f(\lfloor n/2 \rfloor), &n \ge 2 \end{cases} $$ Note that you've given $f(1)=0$, not $f(0)=1$. Hence, trivially, $f(n)=0$ for all positive integers $n$. All the options given in the question are correct, and the best answer might be the tighest bound among the answers, which is $O(\log_2 n)$.

However, if there's a typo in your question and you meant $f(0)=1$, then that's a nontrivial recurrence. So suppose $f(0)=1$, and $f(n)=f(n-1)+f(\lfloor n/2 \rfloor), \forall n \ge 1$. In [Knuth, "An almost linear recurrence", Fibonacci Quarterly, 1966] it is proved that for any power $k$, there exists an integer $N_k$ such that $f(n) > n^k$for all $n \ge N_k$. Thus, $f(n)$ grows faster than a polynomial of any degree. Your guess $f(n)=O(2^n)$ is correct, but that upper bound is not tight. To verify this, observe that the given sequence grows more slowly than the Fibonacci sequence, which grows like $1.618^n$. Alternatively, it is proved in said paper that $f(n)$ grows more slowly than $\alpha^n$ for any $\alpha > 1$.

$\endgroup$
2
  • $\begingroup$ I like this answer, that's what I thought as well. Depending on how the question is interpreted. If we're asking Big-O of the value of f(n), then all answers are correct. But if we're talking about how many iterations/recursions are performed, then none of the answers are correct. However, if we're asking how many iterations/recursions, assuming we're using dynamic programming or caching. Then O(n) is the most-correct/tightly-bound option. $\endgroup$ Commented May 6 at 2:16
  • 1
    $\begingroup$ That's a good point. There's a difference between asking for the complexity of the function and the complexity of the running time of the above program. My answer looks at the former while the accepted answer looks at the latter. We can't assume dynamic programming is being used because it isn't. If it were, the code would be different and would contain some kind of memoization: if n is in a dictionary d, then return d[n], else do the computation mentioned. $\endgroup$ Commented May 7 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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