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:

    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)
     
    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Starnge Recursion algorithm definition
  1. Bernoulli Recursions (Replies: 2)

  2. Integral: recursion (Replies: 12)

  3. Simple recursion (Replies: 3)

Loading...