[Quema]

Me piden una cota asintótica superior de \( T(n) \) siendo constante para \( n\leq{}2 \) de:

1) \( T(n)=T(\sqrt[ ]{n})+1, \)
2) \( T(n)=T(n-1)+n. \)

¿Cómo se halla?

[Luis Fuentes]

Hola

Me piden una cota asintótica superior de \( T(n) \) siendo constante para \( n\leq{}2 \) de:

1) \( T(n)=T(\sqrt[ ]{n})+1, \)
2) \( T(n)=T(n-1)+n. \)

¿Cómo se halla?

Para la primera si haces \( n=e^x \) y llamas \( f(x)=T(e^x) \) tienes:

\( f(x)=T(e^x)=T(\sqrt{e^x})+1=f(x/2)+1 \)

Entonces \( f(x)\sim O(log(x)) \), mira por aquí :

https://math.stackexchange.com/questions/1266747/how-to-solve-the-recurrence-tn-t-n-2-1-is-olg-n

y \( T(n)=f(log(n))\sim O(log(log(n)) \).

El segundo se puede resolver explícitamente. No se si conoces los métodos de resolución de recurrencias lineales. Obtendrás que:

\( T(n)=\dfrac{1}{2}(n^2+n)+cte \)

Por tanto \( T(n)\sim O(n^2) \).

Saludos.