How to solve the recurrence relation $T(n) = T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + 2$

Question

I'm trying to solve a recurrence relation for the exact function (I need the exact number of comparisons for some algorithm). This is what i need to solve:

$$\begin{aligned} T(1) &= 0 \\ T(2) &= 1 \\ T(n) & = T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + 2 \qquad(\text{for each $n\ge2$}) \end{aligned}$$

Without the ceiling and floor I know that the solution is $T(n) = 3n/2 -2$ if $n$ is the power of 2, but how can I solve it with them? (and for every $n$, not just $n$ that is the power of 2).

Thanks a lot.

Answer 1

As mentioned in comment, the first two conditions $T(1) = 0, T(2) = 1$ is incompatible with the last condition $$\require{cancel} T(n) = T(\lfloor\frac{n}{2}\rfloor) + T(\lceil\frac{n}{2}\rceil) = 2\quad\text{ for } \color{red}{\cancelto{\;\color{black}{n > 2}\;}{\color{grey}{n \ge 2}}} \tag{*1}$$ at $n = 2$. We will assume the condition $(*1)$ is only valid for $n > 2$ instead.

Let $\displaystyle\;f(z) = \sum\limits_{n=2}^\infty T(n) z^n\;$ be the generating function for the sequence $T(n)$. Multiply the $n^{th}$ term of $(*1)$ by $z^n$ and start summing from $n = 3$, we obtain:

$$\begin{array}{rrl} &f(z) - z^2 &= T(3) z^3 + T(4) z^4 + T(5) z^5 + \cdots\\ &&= (T(2) + 2)z^3 + (T(2) + T(2) + 2)z^4 + (T(2)+T(3)+2)z^5 + \cdots\\ &&= (1+z)^2 ( T(2)z^3 + T(3)z^5 + \cdots) + 2(z^3 + z^4 + z^5 + \cdots)\\ &&= \frac{(1+z)^2}{z}f(z^2) + \frac{2z^3}{1-z}\\ \implies & f(z) &= \frac{(1+z)^2}{z}f(z^2) + z^2\left(\frac{1+z}{1-z}\right)\\ \implies & \frac{(1-z)^2}{z} f(z) &= \frac{(1-z^2)^2}{z^2}f(z^2) + z(1-z^2) \end{array} $$ Substitute $z^{2^k}$ for $z$ in last expression and sum over $k$, we obtain

$$f(z) = \frac{z}{(1-z)^2}\sum_{k=0}^\infty \left(z^{2^k} - z^{3\cdot2^k}\right) = \left( \sum_{m=1}^\infty m z^m \right)\sum_{k=0}^\infty \left(z^{2^k} - z^{3\cdot2^k}\right)$$

With this expression, we can read off $T(n)$ as the coefficient of $z^n$ in $f(z)$ and get

$$T(n) = \sum_{k=0}^{\lfloor \log_2 n\rfloor} ( n - 2^k ) - \sum_{k=0}^{\lfloor \log_2(n/3)\rfloor} (n - 3\cdot 2^k)$$

For $n > 2$, we can simplify this as $$\bbox[4pt,border: 1px solid black;]{ T(n) = n \color{red}{\big(\lfloor \log_2 n\rfloor - \lfloor \log_2(n/3)\rfloor\big)} - \color{blue}{\big( 2^{\lfloor \log_2 n\rfloor + 1} - 1 \big)} + 3\color{blue}{\big( 2^{\lfloor \log_2(n/3)\rfloor +1} - 1\big)}}\tag{*2}$$

There are several observations we can make.

• When $n = 2^k, k > 1$, we have $$T(n) = n(k - (k-2)) - (2^{k+1} - 1) + 3(2^{k-1} - 1) = \frac32 n - 2$$

• When $n = 3\cdot 2^{k-1}, k > 0$, we have $$T(n) = n(k - (k-1)) - (2^{k+1} - 1) + 3(2^k - 1) = \frac53 n - 2$$

• For $2^k < n < 3\cdot 2^{k-1}, k > 1$, the coefficient for $n$ in $(*2)$ (i.e the factor in red color) is $2$, while the rest (i.e those in blue color) didn't change with $k$. So $T(n)$ is linear there with slope $2$.

• For $3\cdot 2^{k-1} < n < 2^{k+1}, k > 1$, the coefficient for $n$ in $(*2)$ is now 1. Once gain $T(n)$ is linear there but with slope $1$ instead.

Combine these, we find in general

$$\frac32 n - 2 \le T(n) \le \frac53 n - 2 \quad\text{ for }\quad n > 2$$ and $T(n) = O(n)$ as expected. However, $\frac{T(n)}{n}$ doesn't converge to any number but oscillate "between" $\frac32$ and $\frac53$.

Above is a picture ilustrating the behavior of $T(n)$. The blue pluses are the value of $T(n) - (\frac32 n - 2)$ computed for various $n$. The red line is $\frac{n}{6} = (\frac53 n - 2) - (\frac32 n - 2)$. As one can see, $T(n)$ doesn't converge to any straight line. Instead, it oscillate between lines $\frac32 n - 2$ and $\frac53 n - 2$ as discussed before.

Answer 2

I think all you have to do is to change $T(1)=0$ to $T(1)=-1/2$.

We can prove that the following holds for every $n\ge 1$ by induction. $$T(n)=\frac{3n}{2}-2\tag1$$

For $n=1$, it holds trivially.

For $n=2$, it holds trivially.

Suppose that it holds for $n,n+1(n\ge 1)$. Then, $$T(2n)=2T(n)+2=2\left(\frac{3n}{2}-2\right)+2=3n-2=\frac{3(2n)}{2}-2,$$ $$T(2n+1)=T(n+1)+T(n)+2=\frac{3(n+1)}{2}-2+\frac{3n}{2}-2+2=\frac{3(2n+1)}{2}-2.$$ Hence, we know it holds for $2n, 2n+1$

Therefore, $(1)$ holds for every $n\ge 1$. Q.E.D.

Answer 3

A common problem solving strategy is to solve a simpler problem, then figure out how the actual problem differs from the simpler one.

You've already worked out that the powers of $2$ satisfy $T(n) = 3n/2 - 2$. (Actually that's not correct, because $T(1) \neq -1/2$, but we'll ignore that for now)

So there's your simpler solution: $T$ looks like $3n/2 - 2$, and now your job is to figure out exactly what the difference is.

To that end, define $S(n) = T(n) - (3n/2 - 2)$, and figure out what recurrence $S$ satisfies; it will be a lot simpler than the one for $T$.

Answer 4

We suppose that $T(n)=O(n)$

So, $\exists c,b>0 \text{ and } n_0 \geq 1 \text{ such that } \forall n \geq n_0:$

$$T(n) \leq cn-b$$

Suppose that the hypothesis stands also for $\lfloor \frac{n}{2} \rfloor$ and $\lceil \frac{n}{2} \rceil$:

$$T(\lfloor \frac{n}{2} \rfloor) \leq c\lfloor \frac{n}{2} \rfloor-b \\ T(\lfloor \frac{n}{2} \rfloor) \leq c\lceil \frac{n}{2} \rceil-b $$

Then:

$$T(n) \leq c\lceil \frac{n}{2} \rceil-b+c\lfloor \frac{n}{2} \rfloor-b+2=c(\lceil \frac{n}{2}+\lfloor \frac{n}{2} \rfloor)-2b+2 \\ =cn-b-(b-2) \leq cn-b \text{ if } b \geq 2 $$

Therefore, $T(n)=O(n)$.

Answer 5

Lemma. $T(n+1)-T(n)=\begin{cases}2&\text{if $2\cdot 2^k\le T(n)<3\cdot 2^k$ for some $k\in\mathbb Z$}\\1&\text{otherwise}\end{cases}$

Proof. This is directly verified for $n\le 3$. For larger $n$, we have $$T(n+1)-T(n)=T(\lceil\frac{n+1}2\rceil)+T(\lfloor\frac{n+1}2\rfloor)-T(\lceil\frac{n}2\rceil) -T(\lfloor\frac{n}2\rfloor)$$ If $n=2m$ is even, this is $T(m+1)-T(m)$. And if $n=2m+1$ is odd, it is $T(m+1)-T(m)$ again. As in both cases, $n$ has the same two leading digits as $m$, the claim follows by induction. $_\square$

Corollary. Let $n=2^k+r$ with $0\le r<2^k$. Then $$T(n)=\begin{cases}3\cdot2^{k-1}+2r&\text{if $r<2^{k-1} $}\\ 2^{k+1}+r&\text{if $r\ge 2^{k-1} $}\end{cases} $$

Proof. By induction using the lemma. $_\square$

Especially, $T(n)/n$ oscillates as also found by achille hui, taking the value $3/2$ for $r=0$ and $5/3$ for $r=2^{k-1}$