Search code examples
recurrence

#Recurrence T(n)=3T(n/3)+Ѳ(log₃n)

Sorry I have tried a lot to solve this recurrence equation T (n) = 3T (n / 3) + Ѳ (log3n) with the replacement method but I can not get the required result:

1) T (n) = O (nlogn)

2) Induction Base: for every n = 1 -> 1log1 + 1 = 1 = T (1)

  Inductive step: T (k) = klogk + k for each k <n

 Use k = n / 3

T (n) = 3T (n / 3) + Ѳ (log₃n)

1) T (n) = O (nlogn)

2) Induction

 Base: for every n = 1 -> 1log1 + 1 = 1 = T (1)

  Inductive step: T (k) = klogk + k for each k <n

 Use k = n / 3

T (n) = 3T (n / 3) + Ѳ (log₃n)

= 3 [n / 3logn / 3 + n / 3] + (log₃n)

= nlogn / 3 + n + (log₃n)

= n(logn-log3) + n + (log₃n)

= nlogn-nlog3 + n + (log3n)

Solution

  • Firstly we can (eventually) ignore the base 3 in the Theta-notation, as it amounts to a multiplicative factor as is therefore irrelevant. Then we can try the following method:

    1. Hypothesis by inspection:

    If we re-substitute T into itself multiple times, we get:

    enter image description here

    What is the upper limit m? We need to assume that T(n) has a stopping condition, i.e. some value of n where it stops recursing. Assuming that it is n = 1 (it really doesn't matter, as long as it's a constant much smaller than n). Continuing (and briefly restoring the base 3):

    enter image description here

    Surprisingly the answer is not Ө(n log n).

    2. Induction base case

    We don't use induction to prove the final result, but the series result we deduced by inspecting the behaviour of the expansion.

    For the base case n / 3 = 1, we have:

    enter image description here

    Which is consistent.

    3. Induction recurrence

    enter image description here

    Again, consistent. Thus by induction the summation result is correct, and T(n) is indeed Ө(n).

    4. Numerical tests:

    Just in case you still cannot believe that it is Ө(n), here is a numerical test to prove the result.

    Javascript code:

    function T(n) {
   return n <= 1 ? 0 : 3*T(floor(n/3)) + log(n);
}

    Results:

    n           T(n)
--------------------------
10          5.598421959
100         66.33828212
1000        702.3597066
10000       6450.185742
100000      63745.45154
1000000     580674.1886
10000000    8924162.276
100000000   81068207.64

    Graph:

    enter image description here

    The linear relationship is clear.