Comprensión del problema Teorema maestro

Question

Estoy estudiando el teorema del maestro (para el análisis de algoritmos recursivos) y entiendo perfectamente por qué una búsqueda binaria es de orden $\log_2(n)$ .

También entiendo que si lo formulamos como $T(n) aT(\frac{n}{b}) + cn^d$ el término recursivo es $O(a^{\log_b(n)})$ y $cn^d$ es $O(n^d)$ .

Lo que no entiendo es dónde está el $e = \log_b(a)$ utilizado en la comparación con $d$ viene de. En la comparación entre el término de tiempo de ejecución y el término recursivo comparamos $n^d$ contra $n^{\log_ba}$ y este último término no lo entiendo:

¿Cómo podemos transformar $a^{\log_b(n)}$ en $n^{\log_ba}$ ?

Answer 1

$$a^{\log_bn}=a^{\log n/\log b}=\exp\left(\log a\cdot\frac{\log n}{\log b}\right)=n^{\log a/\log b}=n^{\log_ba}$$