Search code examples
big-orecurrencelogarithm

How can i solve the recursion T(n) = 5T(n/7) + logn?

I'm trying to solve the recursion T(n) = 5*T(n/7) + log(n) , T(1) = Theta(1)

I tried using the recursive tree method but i got stuck trying to find the height of the tree and i don't know how to apply the Master Theorem here as i have log(n). Thank you for your time .

Solution

  • You've asked two questions here:

    1. What is the depth of the recursion tree?

    2. How do you solve the recurrence relation using the Master Theorem?

    For question (1), if you're trying to size up a recursion tree, it helps to watch what happens to the size of the input as the recurrence runs. For example, after zero recursive expansions, we have T(n). After one recursive expansion, we have

    T(n) = 5T(n / 7) + log n,

    and notice that the argument to T is n / 7. After two recursive expansions, we get

    T(n) = 25T(n / 49) + 5 log (n / 7) + log n,

    where the argument to T is now n / 49. After a third recursive expansion, we get

    T(n) = 125T(n / 343) + 25 log(n / 49) + 5 log (n / 7) + log n,

    and the argument to T is now n / 343.

    A good question to think about: if you are i iterations deep in this recurrence, what will the argument to T be? And given that the recurrence stops when the argument is 1, how can you solve for the value of i where the recursion terminates?

    To your second question - how do you use the Master Theorem here? - applying the Master Theorem directly to this problem is a bit tricky because of the logarithmic term. A useful technique you can use when you have log terms that you'd like to make disappear is to sandwich the recurrence between two other, simpler recurrences. Notice, for example, that T(n) is sandwiched between these two recurrences:

    L(n) = 5L(n / 7) + n0

    U(n) = 5L(n / 7) + nε, for any ε > 0.

    These recurrences much more directly fit into the Master Theorem, and if you're clever with how you choose ε (hint: make it really, really small!), you can show that L(n) and U(n) both give the same asymptotic bound. Since T(n) is sandwiched between the two of them, this means that T(n) will also have that same asymptotic growth, and you'll have your answer.

    Hope this helps!