La recurrencia de la $T(n)=T(n/2)+2^n$$T(n)=T(n/2+\sqrt n)+\sqrt{6044}$ , sin (!) el maestro método

Question

Dada la Recurrencia $$T(n)=T(n/2)+2^n$$ y $$T(n)=T(n/2+\sqrt n)+\sqrt{6044}$$

Comentario : $T(n)=1$ $n\le 3$

Estoy tratando de encontrar su límite superior y límite inferior , que es, probablemente, $O(2^n)$ para la primera.

He tratado de adivinar la solución de la primera ($T(n)=T(n/2)+2^n$) pero no funciona , luego he probado el lugar $m = 2^n$ por lo tanto $n=\log(m)$ y el uso de la nueva ecuación, pero todavía no funciona .

Para el segundo ($T(n)=T(n/2+\sqrt n)+\sqrt{6044}$) estoy tratando de adivinar que $T(n)=O(n)$ , por lo tanto $T(n)≤c\cdot n$ , pero todavía no funciona.

Las sugerencias y/o las direcciones sería muy apreciada .

Saludos

EDITAR:

Sobre el segundo :

$T(n)≤c(n/2+√n)+√6044=cn/2+c√n+√6044=(cn-cn/2)+c√n+√6044= cn-cn/2+c√n+√6044=cn(cn/2-c√n√6044) ≤^? cn$

Lo cual es cierto sólo si $(cn/2-c√n-√6044)>0$ . Qué te parece , amigos ?

Answer 1

$T(n)=T(n/2)+2^n$ puede ser visto a menos de $2^{n+1}$,$O(2^n)$.

Para el segundo, observe que:

$T(n)=T(n/2+\sqrt{n})+\sqrt{6044}$

$\le n/2+\sqrt{n}+\sqrt{6044}$ desde que supongo que es lineal

$\le n$ grandes $n$, debido a $\sqrt{n}$+constante crece más lento de lo $n$.

Answer 2

Una mejor estimación de la primera es $T(n) = 2^{n} + O(2^{n/2})$. O la misma idea de iteración para dar una cadena de previsiones como $T(n) = 2^n + 2^{n/2} + 2^{n/4} + O(2^{n/8})$.