# Tag Info

FastPower will compute $a^b$ using the following recurrence: $$$$a^b=\begin{cases}a & \text{if }b=1\\ (a^2)^{\frac{b}{2}} & \text{if }b\text{ is even}\\ a\cdot(a^2)^{\frac{b-1}{2}} & \text{if }b\text{ is odd}\end{cases}$$$$ This is $O(\log{b})$ since $b$ decreases by at least a factor of $2$ each recursive call. This ...
Alternatively, you can substitute $$n = \log{(m)} \tag{1}$$ Then $$2^n = 2^{\log{(m)}} = m \tag{2}$$ Our original problem becomes $$t(n) = 4t(\underbrace{n/2}_{ \log{(m)} / 2\\=\log{(m)}-\log{(2)}\\=\log{(m)}-1 }) + 2^n \tag{3}$$ $$t(\log{(m)}) = 4 t(\log{(m)}-1)+m \tag{4}$$ At this point, we can substitute $n$ back in place of $\log{(m)}$: t(n) = 4 t(...