1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Starnge Recursion algorithm definition

  1. Apr 20, 2012 #1
    I'm reading the book "Algorithms Design" and a recursion algorithm is defined as:


    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)
    Last edited: Apr 20, 2012
  2. jcsd
  3. Apr 20, 2012 #2
    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook