Search code examples
algorithmrecursionasymptotic-complexity

Recursion tree for recursive equation

I have this recursive equation: T(n) = T(n/2) + T(n/5) + T(n/9) + Θ(n)

I draw my recursion tree like this:

          cn
     /     |     \
   n/2    n/5    n/9
  / | \  / | \  / | \
  ..................

The tree has log(n) + 1 levels, each level has 3 times more nodes than the level above, and subproblem sizes decrease by a factor of 2 each time. Now this is how I see the total cost is:

enter image description here

I forgot to put this: Is my solution correct?

Solution

  • Suppose we have the slightly more general relation:

    enter image description here

    Where f(n) is some function, e.g. cn.

    If we re-substitute this relation into itself, i.e. each of the recursive calls, the next layer of recursive calls produced will have its parameter multiplied by the corresponding factor:

    enter image description here

    If we continue, the pattern is given by this expression:

    enter image description here

    ... i.e. a Trinomial expansion. The coefficients of each T term is given by the trinomial coefficients, and the argument by the different powers of λμν:

    enter image description here

    As you can see from the expansion, the f-terms are one level of recursion behind the T-terms. So, the sum of all f-terms, taking into consideration that they must be accumulated unlike the T-terms:

    enter image description here

    All of the above can be proven by induction, and are generalizable to any number of recursive calls.

    When do we terminate, i.e. get rid of the T-terms? As I said in my comment, when recursion reaches the end of the longest path. This is given by considering the slowest decreasing term (as you correctly deduced):

    enter image description here

    Thus the time complexity function's tightest closed-form bound is given by:

    enter image description here

    This is very easy to evaluate if f(n) is some power of n.

    For the example, f(n) = Θ(n), α = β = γ = 1, λ = 2, μ = 5, ν = 9. Thus:

    enter image description here

    The term inside the brackets is exactly the trinomial expansion from earlier. Thus:

    enter image description here

    Since τ < 1, the exponential term vanishes. Therefore T(n) = O(n).

    Numerical tests to confirm this:

    n         T(n)
-----------------------------
10        21.86111111
100       328.1442901
1000      3967.333431
10000     44150.87621
100000    471262.9357
1000000   4910520.041
10000000  50415530.84

    log-log plot of T(n) against n:

    enter image description here

    The gradient is 1.054 ± 0.01166, which is very close to the theoretical value of 1, thus strongly supporting the result of T(n) = O(n).