23
$\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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
18
$\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)$.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Sep 9, 2012 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
    Commented Sep 9, 2012 at 21:17
  • $\begingroup$ Ah ok, that last edit did it for me. It's clear now, thanks! $\endgroup$
    – goooser
    Commented Sep 9, 2012 at 21:24
  • 2
    $\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
    Commented Dec 23, 2015 at 3:42
  • $\begingroup$ @Atinesh You can try with different m values. The m values in the S(m)=2S(m/2)+m. are all the same m. S(m) will be translated into T(2^m) in the end. $\endgroup$
    – xianshenglu
    Commented Sep 11, 2022 at 17:01
7
$\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)\,.$$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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