19
$\begingroup$

Currently, I am self-studying Intro to Algorithms (CLRS) and there is one particular method they outline in the book to solve recurrence relations.

The following method can be illustrated with this example. Suppose we have the recurrence

$$T(n) = 2T(\sqrt n) + \log n$$

Initially they make the substitution m = lg(n), and then plug it back in to the recurrence and get:

$$T(2^m) = 2T(2^{\frac{m}{2}}) + m$$

Up to this point I understand perfectly. This next step is the one that's confusing to me.

They now "rename" the recurrence $S(m)$ and let $S(m) = T(2^m)$, which apparently produces

$$S(m) = 2S(m/2) + m$$

For some reason it's not clear to me why this renaming works, and it just seems like cheating. Can anyone explain this better?

$\endgroup$

migrated from cstheory.stackexchange.com Sep 9 '12 at 23:15

This question came from our site for theoretical computer scientists and researchers in related fields.

15
$\begingroup$

It's certainly not cheating. Think in calculus how substitution may be used to solve a tricky integral. The substitution makes the equation more manageable for manipulation. Additionally, substitution may transform somewhat complex recurrences into familiar ones.

This is exactly what occurred in your example. We define a new recurrence $S(m)=T(2^m)$. Remember that $T(2^m) = 2T(2^\frac{m}{2}) + m$. Notice that, $S(m/2) = T(2^\frac{m}{2})$. If this particular point is still unclear, let $k =m/2$ and notice all we are doing is this $S(k) = T(2^k)$. Now, we can express $S(m)$ by expanding it to: $$ S(m) = 2S(m/2) + m.$$ Solving for $S$ we see that it resolves to our familiar friend $O(m \log m)$. Now that we've solved $S$ we want to express this in terms of $T(n)$. To do this, merely plug back in our original value for $m$ and we have $T \in O(\log n \log \log n)$.

$\endgroup$
  • $\begingroup$ Right, I totally understand how substitution helps make problems easier and how to plug values back in to obtain the complexity in terms of n. I guess my question is, after letting S(m) = T(2^m), how do you derive S(m/2)? It's just non-obvious to me for some reason. To be more specific, how do you conclude that T(2^(m/2)) = S(m/2). It seems like in the recurrence T, the subproblem size is being square-rooted, while in the recurrence S, the subproblem size is being halved $\endgroup$ – goooser Sep 9 '12 at 20:58
  • $\begingroup$ The only part I do not understand is when you say "Notice that, S(m/2)=T(2^(m/2))" That's the only part that is non-obvious to me. I'm used to the idea of making variable substitutions, but I'm not really used to the idea of substituting an entire recurrence. $\endgroup$ – goooser Sep 9 '12 at 21:17
  • $\begingroup$ Ah ok, that last edit did it for me. It's clear now, thanks! $\endgroup$ – goooser Sep 9 '12 at 21:24
  • 1
    $\begingroup$ I've a little doubt. If I write function S() in terms of k I'm getting below equation S(k) = 2S(k/2) + m How can I get substitute m for k $\endgroup$ – Atinesh Dec 23 '15 at 3:42
4
$\begingroup$

What $S(m) = T(2^m)$ means is that $S$ and $T$ are two different functions which produce the same result while taking inputs as $m$ and $2^m$ respectively.

Function $S$ can be considered as an operator with two internal steps (otherwise, composition of functions):

  1. $S'$ operator: Input:$m$, Output:$2^m$

  2. $T$ operator(original function): Input:output of first part, Output: As defined originally.

Therefore then transitions are:

$$m\to 2^m\to T(2^m) = S(m)$$ $$\tfrac{m}2\to2^{m/2}\to T(2^{m/2}) = S(\tfrac{m}2)\,.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.