# Time spent multiplying with expoDC and D&C

Let

$$T(m,n) \leq that$$

1. $$0$$ if n = 1
2. $$T(m,n/2) + M(mn/2,mn/2)$$ if n is even
3. $$T(m, n-1) + M(m, (n-1)m)$$ otherwise

The time to do $$a^n$$ where m is the size of a (the number of figures).

If $$M(q,s) \in \Theta(sq^{\alpha -1})$$ for some constant $$\alpha$$ when $$s \geq q$$ prove that

$$T(m,n) \in O(m^\alpha n^\alpha)$$

The problem is from chapter 7 of Fundamentals of Algorithmics from Brassard. I tried to add the $$n-1$$ multiplications but I got $$n^{\alpha + 1}m^{\alpha}$$.