Find one-variable recursive formula for running time of Karatsuba multiplication I'm currently trying trouble to set up the recursive expression for the Karatsuba multiplication of two integers with $n$ and $m$ bits (both having a different number of bits). Usually, the recursion for two $n$ bit integers for Karatsuba multiplication would be:

$T_{n} = \begin{cases} 3T_{n/2} + cn &amp;\mbox{if } n &gt; 1 \\ 1 &amp;\mbox{if } n = 1\end{cases}$

However, when working with two integers with different number of bits, the expression would be different, as we would have $T_{n,m}$ as a recursion. Is there any way to reduce the problem of setting up the recursion in terms of only one variable $n$? I was thinking of letting $T_{n}$ be the maximum number of operations with the pairs $(n,m)$, and basically giving the same recursive formula as stated above. Would that change the running time of the program or is there a more clever way to change it into a one variable recursion?
The recurrence with two variables $n,m$ is as what you have obtained:

$$T(n, m) = 3T(n/2, m/2) + O(\max(n,m))$$

Assume $n = \Omega(m)$. We have

$$T(n, m) = 3T(n/2, m/2) + O(n)$$

Although the master theorem cannot be applied directly, if you expand this recurrence, then you will eventually identify the patterns and the result:

$$T(n, m) = 3T(n/2, m/2) + O(n) = \cdots = \sum_{k=?}^{k=?} (3/2)^{k} \cdot O(n) + c \cdot T(n/m,1) = \cdots$$
Please find out $c$ and the range of $k$, and fill the gaps.



There is a method to reduce the two variables $n,m$ recurrence to a single one:


  Assume $n = \max(n,m)$ and pre-append $n-m$ $0$'s to the integer with less bits. 


The problem is this will yield a different time complexity from that given above. This can be seen from an extreme example: $1$-bit $\times$ $O(n)$-bit.