0
$\begingroup$

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}$.

Any advice?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.