Asymptotic Equivalence of Another Recurrence:

Question

So I have the following recurrence relation:

$$f(n) = f(n-1) + f(\lceil n/2\rceil)+ 1$$

I already know that:

If:

$$g(n) = g(n-1) + 1$$

$$g(n) = O(n)$$

If:

$$g(n) = g(\lceil n/2\rceil) + 1$$

$$g(n) = O(\log(n))$$

If:

$$g(n) = g(n-1) + g(\lceil n/2\rceil)$$

$$g(n) = O(nlog(n))$)

Thus can I definitely conclude that:

$$f(n) = O(n \log(n) * n * \log(n)) = O(n^2 \log(n)^2)$$

Answer 1

You have $f(n) = f(n-1) + f(\lceil n/2\rceil)+ 1$. So, if you define $f(0)=0$

$$f(n)=\displaystyle\sum_{k=1}^n(f(k)-f(k-1))$$ $$=\displaystyle\sum_{k=1}^nf(\lceil k/2\rceil)+ n$$ $$=O(n\log n)+n=O(n\log n)$$

As, $\displaystyle\sum_{k=1}^ng(\lceil k/2\rceil)=g(n)=O(n\log n)$, when $g(n) = g(n-1) + g(\lceil n/2\rceil)$.