# Starnge Recursion algorithm definition

1. Apr 20, 2012

### xeon123

I'm reading the book "Algorithms Design" and a recursion algorithm is defined as:

T(n)$\leq$qT(n/q)+cn

But in the Karatsuba’s Algorithm, the recurrence for this algorithm is
T (n) = 3T (n/2) + O(n) = O(nlog2 3).

The last equation is strange, since 3T(n/2) is bigger than the set. Why they define like that?

Last edited: Apr 20, 2012
2. Apr 20, 2012

### xeon123

I get the solution. The solution is related to the problem.

The karatsuba algorithm is a faster way to multiply 2 numbers. It splits the numbers in 2 halves.

The halves of the numbers is composed in the following equation:

XY = ac2^n + (ad + bc)2^n/2 + bd.

This equation is split in 3 subproblems: ac, bd, (a − b)(c − d).

So, the recurrence of the algorithm will become

T(n) = 3T(n/2) + cn