Qual é a complexidade da multiplicação?

Não conheço nenhum algoritmo melhor do que o FFT.

Esclarecendo: com "tem pelo menos essa complexidade" você quer dizer que isso é uma cota superior, claramente.

Esse algoritmo é uma divisão e conquista que segue a mesma linha do algoritmo de Strassen pra multiplicação de matrizes. O truque está na forma como a recursão é fórmulada, a ideia é mesmo do algoritmo de Strassen (Tem no Cormen). Claro, isso não muda a cota inferior dada pelo FFT, já que \(n \log n \leq n^{\log_2{3}}\). O grau de \(n\) neste algoritmo do AHO é \(\log_2{3}\)

Não entendi a parte da soma das meias multiplicações. Por que ele soma AC e BD e depois subtrai exatamente AC e BD de novo? (A propósito, suponho aqui que AB é a concatenação de A e B, e A*B é a multiplicação, certo?)

Segundo a Wikipedia ( http://en.wikipedia.org/wiki/Karatsuba_algorithm ):

x = x1*10 + x0 (ou seja, pra um número AB, x1 seria A e x0 seria B)
y = y1*10 + y0 
z2 = x1y1
z1 = x1y0 + x0y1
z0 = x0y0 
xy = (x1*10 + x0)(y1*10 + y0) = z2*10² + z1*10 + z0

Pra números maiores, se faz recursivamente. Na página da Wikipedia mencionada acima há algumas curiosidades, como evitar uma das multiplicações acima.