Time spent multiplying with expoDC and D&C

18 Views Asked by At

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)$

Any advice?