[Frankie]

Buenas, estoy ante un problema que dice así:

El tiempo de ejecución de un algoritmo A está descrito por la recurrencia:
\( T(n) = 7T(n/2) + n^2 \)

otro algoritmo B tiene un tiempo de ejecución dado por:
\( T'(n) = aT' (n/4) + n^2 \)

¿cuál es el mayor valor de la constante a que hace a B asintóticamente más rápido que A?

He procedido a resolver la primera recurrencia:

Cambio de variable \( n= 2^k \)
\(
T(2^k) = 7T(2^{k-1}) + 4^k \)
\( T_k = 7_{Tk-1} + 4^k \)

Raíces \( (x-7)(x-4) = 0 \rightarrow{c_1 7^k + c_2 4^k} \)
Resultado \( c_1 7^{lg n} + c_2 n^2 \)

Para la segunda he aplicado el mismo procedimiento

Cambio de variable \( n= 4^k \)
\(
T'(4^k) = aT'(4^{k-1}) + 16^k \)
\( T'_k = a_{T'k-1} + 16^k \)

Raíces \( (x-a)(x-16) = 0 \rightarrow{c_1 a^k + c_2 16^k} \)
Resultado \( c_1 a^{lg n} + c_2 n^2 \)

Mi idea ahora es igualar las dos ecuaciones, quedando lo siguiente después de despejar:
\( 7^{lg n} = a^{lg n} \)

A raíz de aquí no se seguir, no encuentro la forma de despejar esa ecuación tan simple... Perdón por la duda tan tonta.

[Masacroso]

Pues puedes aplicar la función exponencial a ambos lados, que es biyectiva, y te queda la ecuación \( \log n\cdot \exp(7)=\log n\cdot \exp(a)\iff \exp(7)=\exp(a)\iff 7=a \) para \( n>1 \), ya que tanto la función exponencial como el logaritmo son biyecciones, y por tanto mantienen las soluciones de la ecuación, de ahí el símbolo "\( \iff \)".

Otra forma de ver lo mismo es observar que \( a^{\log n}=\exp(\log a\cdot\log n)=n^{\log a} \) para cualquier \( a>0 \), es decir, tu ecuación es equivalente a esta otra: \( n^{\log a}=n^{\log 7} \).

[Frankie]

Resolví la parte más compleja y me atasqué en la más fácil...

Muchísimas gracias. Tenga un buen día.