Special case of Karatsuba algorithm

Question

I need some help with the following problem:

Let's consider a computer with word length of sqrt(n) bits. That means that any multiplication between 2 sqrt(n)-bit integers is O(1). The problem is to prove that the complexity of doing with this computer the multiplication of 2 n-bit integers using the Karatsuba algorithm is O(n^1.29).

I have tried to write a recursive relation like: T(sqrt(n)) = 3T(sqrt(n)/2) + Θ(sqrt(n))

Then, by replacing sqrt(n) with n, I end up with: T(n) = 3T(n/2) + Θ(n) which gives T(n) = Θ(n^1.58).

I can't understand where I have made a mistake. Thank you very much!!

Answer 1

You have correctly stated that the original recurrence relation is T(n) = 3T(n/2) + Θ(n); the logical error you made was to directly replace n with sqrt(n).

What you must instead do here is re-derive the time complexity with a different stopping condition - i.e. T(m) = O(1) Ɐ m ≤ sqrt(n). The given result T(n) = Θ(n^1.58) follows from making the stopping condition equal to some small constant, which is not the case here.

Let's repeatedly expand this recurrence:

... and apply the modified stopping condition:

... using some logarithm laws. And thus we arrive at:

... which is the required result.