algorithms - When not to assume $n$ is a power of 2, while solving recurrences?

Question

In Udi Manber - Introduction to Algorithms. A Creative Approach, exercise 3.29, p.59

Although in general it is sufficient to evaluate recurrence relations only for powers of 2, that is not always the case. Consider the following relation:

$$T\left(n\right)=\begin{cases} T\left(\frac{n}{2}\right)+1 & \text{if $n$ is even}\\ 2T\left(\frac{n-1}{2}\right) & \text{if $n$ is odd} \end{cases}$$

a. Prove that the solution of this recurrence for powers of $2$ is $T\left(2^{k}\right)=k+1$ (namely, for powers of $2$, $T\left(n\right)=O\left(\log n\right)$)

b. Show that, for an infinite number of values of $n$, $T\left(n\right)=\Omega\left(n\right)$. Discuss why the usual assumption about the relative behavior for powers of $2$ and nonpowers of $2$ breaks down for this recurrence.

I have no problem solving this problem, but there an important section of the solution provided in the book make me confused, and I can't search for explanations on the Internet or books about that:

We can restrict ourselves to powers of $2$ if the solution of the recurrence relation is a function that behaves "nicely." In particular, the expressions for the running times of most algorithms are monotonically increasing functions. If the difference between the value of $T\left(n\right)$ and $T\left(2n\right)$ is no more than a constant and if $T\left(n\right)$ is monotonically increasing, then $T\left(m\right)$ for $n < m < 2n$ is no more than a constant times $T\left(n\right)$. Therefore, the analysis for powers of $2$ is sufficient in that case.

---

Here is what I understand about the bold-italic part above:

Consider, $$\begin{align*} T\left(n\right)&=cT\left(\frac{n}{2}\right)+O\left(n\right)\\T\left(2n\right)&=cT\left(n\right)+O\left(2n\right)\\&=c^{2}T\left(\frac{n}{2}\right)+O\left(n\right)\\ \end{align*}$$

The difference between $T\left(n\right)$ and $T\left(2n\right)$ is a constant $c$, and it does not affect the analyzing of $O\left(\right)$ of the recurrence if we chose $2n$ as the input value or any $m$, $n<m<2n$.

Now what I confused is what is the case of not to assume that $n$ is a power of $2$. According to the book, it's not applicable for the case, such as $T\left(n\right)=nT\left(\frac{n}{2}\right)$, when $T\left(2n\right)=2n^{2}T\left(\frac{n}{2}\right)$.

But I see some examples were still solved by this way, such as exercise 8.2.53, p.527 K. Rosen's Discrete Mathematics: $$T\left(n\right)=nT^{2}\left(\frac{n}{2}\right)$$ or this one.

So, my questions are:

1. Am I wrong?

2. Could you provide simple example(s) of monotonic $T\left(n\right)$ where replacing $n$ by a power of 2 is not applicable? (I desire $T\left(n\right)$ have unified formula, without different formulas for specified values of $n$, such as the example provided in Udi Manber's book above).

Thanks!

Answer 1

The way I read it, "the difference between the value of $T(n)$ and $T(2n)$" is $T(2n)-T(n).$ (Actually I would usually write it $T(n)-T(2n),$ but then the rest of it really doesn't make any sense.) So to say this difference is no more than a constant literally means that $T(2n)-T(n)\leq c$ for some constant $c.$

Given the additional condition that $T$ is monotonically increasing, we know that for $n < m < 2n$ we always have $T(n) \leq T(m)\leq T(2n),$ and therefore $T(m) - T(n) \leq c,$ or equivalently $T(m) \leq T(n) + c.$

But "$T(m)$ for $n<m<2n$ is no more than a constant times $T(n)$" means $T(m) \leq cT(n)$ for some constant $c.$

So how do we get $cT(n)$ on the right side instead of $T(n) + k$? I think what the author wanted to say is that the ratio of $T(2n)$ to $T(n)$ is no more than a constant. That covers more functions than the statement the author actually wrote.

Working with the ratio rather than the difference, we can say that $T(2n) \leq cT(n)$ for some constant $c,$ and then the monotonic property tells us that $m<2n$ implies $T(m)\leq T(2n)$ and therefore $m<2n$ implies $T(m)\leq cT(n).$

I don't blame you for finding this confusing. I found it confusing too until I decided the author wrote one thing when they actually should have written something different.

The other thing I think might be missing is the assumption that when we analyze $T(n)$ for powers of $2,$ the function we come up with is also monotonic. In practice that is typically what happens, so it's a good assumption to make.

Once we know that $m<2n$ implies $T(m)\leq cT(n),$ if we find that $T(2^k) \in O(f(2^k))$ (that is, we have done the complexity analysis for $n$ a power of $2$ and found that it is $f(n)$), where $f$ is monotonic, then we know that if $k\geq 1$ and $n = 2^k + 1$ then $$T(n) \leq T(2(n-1)) \leq cT(n-1) \in O(cf(n-1)) = O(f(n)).$$

And likewise for $n = 2^k + r$ where $1 < r < 2^k.$ So the analysis we did for $n$ a power of $2$ gave us the correct complexity class for all values of $n.$

---

For a concrete example where this doesn't work, suppose we have an algorithm that works on an array of length $n,$ but because of the way it is written, the first thing we do if $n$ is not a power of $2$ is to extend the array with dummy elements until its length is a power of $2.$ Then we perform $2^L$ steps where $L$ is the length of the array after extension. That is, $$ T(n) = 4^L \quad \text{where} \quad L = 2^{\lceil \log_2 n\rceil}.$$ Then $m < n \implies T(m) \leq T(n),$ so the function is monotonic.

If $n = 2^k$ then $T(n) = 4^n.$ But if $n = 2^k + 1$ then $T(n) = 4^{2n - 2} \in O(16^n) \neq O(4^n).$ So in this case even thought the function is monotonic, the analysis for $n$ a power of $2,$ never looking at any other value of $n,$ is not sufficient to find the complexity class of the function over all the integers.

Answer 2

For the case of Kenneth Rosen's exercise, I posted an answer's here. As the result of solution 2, I choose $n$ such that $2^{m-1}<n<2^{m}$, in particular, $n=2^{m-1}\cdot2^{\frac{1}{2}}=2^{m-\frac{1}{2}}$. $$\begin{align*} T\left(n\right)&=\frac{n^{2^{\left\lfloor \log_{2}n\right\rfloor }-1}\cdot n^{2^{\log_{2}n-\left\lfloor \log_{2}n\right\rfloor }}}{2^{\left\lfloor \log_{2}n-2\right\rfloor 2^{\left\lfloor \log_{2}n\right\rfloor }+2}\cdot2^{\left(\log_{2}n-\left\lfloor \log_{2}n\right\rfloor \right)2^{\log_{2}n-\left\lfloor \log_{2}n\right\rfloor }}}6^{n}\\&=\frac{n^{2^{m-1}-1}\cdot n^{2^{m-\frac{1}{2}-\left(m-1\right)}}}{2^{\left\lfloor m-\frac{1}{2}-2\right\rfloor 2^{m-1}+2}\cdot2^{\left(m-\frac{1}{2}-\left(m-1\right)\right)2^{m-\frac{1}{2}-\left(m-1\right)}}}6^{n}\\&=\frac{n^{2^{m-1}-1}\cdot n^{\sqrt{2}}}{2^{\left(m-3\right)2^{m-1}+2}\cdot2^{\left(\frac{1}{2}\right)2^{\frac{1}{2}}}}6^{n}\\&\\&=\frac{n^{2^{m-1}-1}\cdot n^{\sqrt{2}}}{2^{\left(m-\frac{1}{2}-3+\frac{1}{2}\right)2^{m-1}+2}\cdot2^{\left(\frac{1}{2}\right)2^{\frac{1}{2}}}}6^{n}\\&=\frac{n^{2^{m-1}}\cdot n^{\sqrt{2}-1}}{4\cdot\left[n\cdot2^{-\frac{5}{2}}\right]^{2^{m-1}}\cdot2^{\left(\frac{1}{2}\right)2^{\frac{1}{2}}}}6^{n}\\&=\frac{n^{2^{m-1}}\cdot n^{\sqrt{2}-1}}{4\cdot n^{2^{m-1}}\cdot2^{-5\cdot2^{m-2}}\cdot2^{\left(\frac{1}{2}\right)2^{\frac{1}{2}}}}6^{n}\\&=\frac{n^{\sqrt{2}-1}}{4\cdot2^{-5\cdot n\cdot2^{-1-\frac{1}{2}}}\cdot2^{\left(\frac{1}{2}\right)2^{\frac{1}{2}}}}6^{n}\\&=\frac{2^{\frac{5n}{2\sqrt{2}}}\cdot n^{\sqrt{2}-1}}{4\cdot2^{\frac{1}{\sqrt{2}}}}6^{n} \end{align*}$$

When, if $n=2^{m}$, $T\left(n\right)=\frac{6^{n}\cdot4^{n-1}}{n}$.

So, I think Udi Manber's statement is right. While I don't exactly know why some recurrences would be solved by replace $n=2^{m}$, but my guess is that it's easier to do, and the results are acceptable (??) (Hope someones would correct it if I was wrong).

Answer 3

For $n = 2m$

$$ t(2m)=t(m+1)+1 \Rightarrow t(m) = c_0 +\log_2 m\\ $$

for $n = 2m+1$

$$ t(2m+1) = 2t(m)\Rightarrow t(m) = c_1(m+1) $$

hence

$$ t(n) = \left(n-2\left\lfloor\frac {n-1}{2}\right\rfloor-1\right)(c_0+\log_2 n)+\left(n-2\left\lfloor\frac {n}{2}\right\rfloor\right)c_1(n+1) $$