Starnge Recursion algorithm definition

[xeon123]

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

T(n)[itex]\leq[/itex]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?

(see pdf https://www.google.pt/url?sa=t&rct=...FrwVhGb_q1zQv1J8g&sig2=tNHJR-cfgZQBnihc7wckJQ)

 

[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