In CLRS 3rd edition P. No 86, the relation

$T(2^{n}) = 2T(2^{n/2}) + n$

is changed to

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

My first question is, why we can change any recurrence relation like this? And, how will the following relation

$T(2^{n}) = T(2^{n-1}) + 1$

be changed? Which change is correct?

$S(n) = S(n/2) + 1$


$S(n) = S(n-1) + 1$


2 Answers 2


"Why we can change any recurrence relation like this?"

Answer: by the definition of function. This is about pure algebra.

Let me explain slowly and clearly. (To someone who just learned the definition of function, I should probably explain much slower with more explanation regarding the definition of domain, range, correspondence, change of dumb variables etc. To someone with a master degree in math, there is really nothing needed to explain. The speed of explanation below is somewhat arbitrarily in-between, since I do not know your level. If you think some stuff is too obvious to you, just skip it. Otherwise, comment below to tell me which part is still puzzling to you.)

Suppose we have a function, $T:\Bbb N\to\Bbb N$ defined by $T(2^{n}) = 2T(2^{n/2}) + n$. Let us define a new function, $S: \Bbb N\to\Bbb N$ by $s(m) = T(2^m)$, that is, $s(1) = T(2)$, $s(2) = T(4)$, $s(3) = T(8)$, etc. Since $m$ is an independent variable, we can also substitute $m/2$ for $m$ to obtain $s(m/2)=T(2^{m/2})$. So we will have, $$s(m) = T(2^m) = 2T(2^{m/2}) + m = 2s(m/2) + m $$

how will the following relation $T(2^{n}) = T(2^{n-1}) + 1$ be changed? Which change is correct? $S(n) = S(n/2) + 1$ or $S(n) = S(n-1) + 1$?

If we define function $S: \Bbb Z\to\Bbb Z$ by $S(m) = T(m)$, i.e., $S$ is the same function as $T$, then we have, for any $n\in\Bbb Z$ that is a power of 2, i.e., $n=2^m$ for some $m$, $$S(n) = S(2^m) = T(2^m) = T(2^{m-1}) + 1 = S(2^{m-1}) + 1 = S(2^m/2)+1 =S(n/2)+1. $$

On the other hand, if we define function $S: \Bbb Z\to\Bbb Z$ by $S(m) = T(2^m)$, then substituting $m-1$ for $m$, we have $S(m-1)=T(2^{m-1})$. So, $$S(m) = T(2^m) = T(2^{m-1}) + 1 = S(m-1) + 1$$

In summary, either one of $S(n) = S(n/2) + 1$ and $S(n) = S(n-1) + 1$ can be correct. Which one is correct depends on how you define $S$. Once you have write down the definition of $S$, it will be clear which one is correct and which one is wrong. In other words, you have to specify what is $S$ first.

  • $\begingroup$ But we call them recurrence relation not recurrence function. Is every recurrence relation a recurrence function? $\endgroup$
    – Mr. Sigma.
    Oct 13, 2018 at 9:11
  • $\begingroup$ Every recurrence relation is about some function. You have to define a function before you can talk about a recurrence relation among values of that function at different points. For example, you can define function $T$ first. You do not have to talk about any recurrence relation. It is possible $T$ does not have any nice recurrence relation. But if it does, then you can talk about the recurrence relations about $T$. $\endgroup$
    – John L.
    Oct 13, 2018 at 9:11

This is just the substitution of variables. Let us say that

$$S(n) = T(2^n)$$

Putting $n/2$ in the above equation we get

$$S(n/2) = T(2^{n/2})$$

Similarly in the second equation you mentioned $S(n) = S(n-1) + 1$ will be correct


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.