3
$\begingroup$

I've read the Wikipedia article explaining the complexity analysis of the Karatsuba algorithm, but I'm not fully grasping it. I seem to have gotten about 75% of the way to the solution on my own, but lack the last 25% to fully understand why the complexity is $O(N^{\log3})$ where the log function is base $2$.

I worked out myself that the recursion tree has height $\log N$ (easy to see), and I understand the coefficient $3$, which can trade places with $N$ due to the properties of logs, comes from the fact that each level of recursion results in three leaves per node of the tree.

I think the main thing that's tripping me up is I'm that not clearly seeing why $\log N$ can be expressed as the exponent of $3$, although I see where $\log N$ and $3$ come from, and I see how in the next step you can swap $N$ and $3$ to get $N^{\log3}$ (something I learned in highschool).

To put this another way, I've been unable to work this problem out to visualize sequentially how this formula plays out for the algorithm. I.E, without already knowing the Master theorem, how does one derive this formula (I assume it's possible) by simply walking through the Karatsuba algorithm and watching the patterns emerge.

UPDATE: In writing out my understanding of the wikipedia explanation line by line to identify where I got stuck, I finally saw the pattern. However, maybe putting it here will help someone else.

$\endgroup$
  • $\begingroup$ I don't quite understand whether setting up or solving the recurrence is your issue. If the latter, this is a duplicate of this question. $\endgroup$ – Raphael Mar 9 '15 at 8:32
  • $\begingroup$ It's not really a duplicate - I'm not really too concerned about solving the problem for different sized integers, but to answer your question, I can create the recurrence tree myself, and I can get the formula for the height of it and also the formula for the number of leaves at the base, but I get stuck after that point. (I'm also aware that each sub-problem itself is a constant - 7). $\endgroup$ – Josiah Mar 9 '15 at 14:22
2
$\begingroup$

"Karatsuba's basic step works for any base B and any m, but the recursive algorithm is most efficient when m is equal to n/2, rounded up."

I understood this to mean that for integers with n digits, m is the ceiling of half n (m being the exponent applied to the Base in the algorithm). This can be seen if you simply look at the definition of the algorithm.

"In particular, if n is $2^k$, for some integer k, and the recursion stops only when n is 1, then the number of single-digit multiplications is $3^k$, which is nc where c = ${\log3}$"

I took this to mean, given n is some power of 2 (2, 4, 8, ...), the number of single digit multiplications performed is 3 * (exponent of 2). I worked out how this conclusion was reached by writing out the tree and finding that each sub-problem involves 3 multiplications, and at the base of the recursive tree, you should have $3^{m - 1}$ sub-problems for that bottom level. However, the -1 can be ignored as, using the properties of exponents, you can factor that out into a constant, which Big-O doesn't consider. Therefore, if we are looking for the exponent of 2, we can get that exponent of 3 as a log relative to n, thus $3^{\log n}$, which by a law of logarithms turns into $n^{\log 3}$. Since the computational complexity of each sub-problem by itself is a constant 7 (4 additions and 3 multiplications) independent of the number of digits in the number representation, the computation itself can be ignored in the efficiency analysis, giving us $O(n^{log 3})$

$\endgroup$
  • 1
    $\begingroup$ Thank you, I was also wondering how the result came about in the Wikipedia article. $\endgroup$ – Abhijit Sarkar Nov 5 '18 at 1:56
  • $\begingroup$ Wikipedia article claims "recursive algorithm is most efficient when m is equal to n/2" but doesn't offer any explanation. Based on the time complexity analysis, I don't see any benefit is the split is taken in the middle, vs say, at one end. Do you? $\endgroup$ – Abhijit Sarkar Nov 5 '18 at 4:47
  • $\begingroup$ @AbhijitSarkar The algorithm requires an additional recursion in relation to n when m != n/2. $\endgroup$ – Josiah Mar 5 at 16:40
2
$\begingroup$

Thank @Josiah for the question and Wiki explanation! To clearly see the runtime of Karatsuba's algorithm for the multiplication of two complex numbers by recursion with Gauss's trick, I would like to add some derivation details:

  • Note that the original runtime $T(n) = 3 T(n/2) + O(n)$. By mathematical induction we can observe that $T(n) = 3^{\log n} + O(n)$, where $\log(.)$ is the logarithm with base $2$
  • Define $x = 3^{\log n}$. Take $log_3(.)$ with base $3$ to both sides we have $\log_3 x = \log n$.
  • By logarithm's change of base, $\log_3 x = \frac{\log x}{\log 3}$ (see Remark below). Thus, $\log x = \log 3 \cdot \log_3 x = \log 3 \cdot \log n = \log n^{\log 3}$. Hence the result follows: $x = n^{\log 3}$ and the runtime $T(n) = O(n^{\log 3}) = O(n^{1.59})$.

Remark: Why $\log_3 x = \frac{\log x}{\log 3}$?

  • Set $y = \log_3 x$. Thus $3^y = x$ and by taking $\log(.)$ to both sides we have $\log 3^y = \log x$.
  • Since $\log 3^y = y \log 3$, we obtain the result: $y = \log_3 x =\frac{\log x}{\log 3}$.
$\endgroup$
  • $\begingroup$ Thanks for posting, though I'm not sure we really need all of that to derive the completely standard fact that $a^{\log b} = b^{\log a}$. $\endgroup$ – David Richerby Nov 29 '17 at 10:58
  • 1
    $\begingroup$ Thanks for sharing the thought. I just would like to summarize the derivation procedure for Karatsuba's algorithm and further provide the nothing-left-out derivations for the logarithm's change of base formula, since somebody may find this helpful (I learned the algorithm from Michael I. Jordan's lecture notes and got stuck at first). :-) $\endgroup$ – bowenli Nov 29 '17 at 17:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.