Equivalencia asintótica de otra recurrencia:

Question

Así que tengo la siguiente relación de recurrencia:

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

Eso ya lo sé:

Si:

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

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

Si:

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

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

Si:

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

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

Así puedo concluir definitivamente que:

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

Answer 1

Usted tiene $f(n) = f(n-1) + f(\lceil n/2\rceil)+ 1$ . Por lo tanto, si se 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)$$

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