Solve the recurrence relation $T(n)^2 = T(n/2)T(2n) - T(n)T(n/2)$

Question

Assume $T(n)$ is positive and non-decreasing function of $n$. Find the recurrence relation:

$$T(n)^2 = T(n/2)T(2n) - T(n)T(n/2).$$

I want to solve this by giving tight $\Theta$-notation bounds in terms of $n$.

Let $S(n)=T(2n)/T(n)$ for $n>2$, then $S(n) = S(n/2) + 1.$ By Master's theorem we have $S(n) = \Theta(\log(n)).$ How to transform this into $T(n)$?

Answer 1

You have already made a lot of progress. Let $S(n)=\frac{T(n)}{T(n/2)}$ for even $n$, similarly to what you defined. If $n=2^kp$ where $p$ is odd, then $$\frac{T(n)}{T(p)}=S\left(2^{k}p\right)S\left(2^{k-1}p\right)\cdots S(2p).$$ It can be easily seen that $S(2^lp)=l+S(2p)-1$, so $$T(n)=T(p)\big(k+S(2p)-1\big)\big(k+S(2p)-2\big)\cdots S(2p)=T(p)\frac{\big(k+S(2p)-1\big)!}{\big(S(2p)-1\big)!}.$$ If the recursion only works for even values of $n$, then this is the only thing we can say. That is, for each odd number $p$, $T(p)$ and $S(2p)$ must be known. However, for a fixed $p$, we can already see that $$T(2^kp)\in\Theta(k!).$$ But I would be cautious and not write $T(n)\in \Theta\big(\log_2(n)!\big)$, because you can define $T(p)$ and $S(2p)$ for each odd $p$ so that $T(n)\notin \Theta\big(\log_2(n)!\big)$.

Suppose now that the recursion is to be interpreted as $$T\big(\lfloor n/2\rfloor \big)^2=T\big(\lfloor n/4\rfloor\big)T(n)-T\big(\lfloor n/2\rfloor\big)T\big(\lfloor n/4\rfloor\big)$$ for all positive integers $n\ge 4$. We set $S(n)=\frac{T(n)}{T\big(\lfloor n/2\rfloor\big)}$ for $n\ge 2$, so $S(n)=S\big(\lfloor n/2\rfloor\big)+1$ for $n\geq 4$. Then we can show by induction that $$S(n)=\left\{\begin{array}{ll}S\big(2^{k}\big)=k+S(2)-1&\text{if }2^k\leq n < 3\cdot 2^{k-1}\\ S\big(3\cdot 2^{k-1}\big)=k+S(3)-1&\text{if }3\cdot 2^{k-1}\leq n<2^{k+1}.\end{array}\right.$$ This means $$T(n)=\left\{\begin{array}{ll}T(1)\frac{\big(k+S(2)-1\big)!}{\big(S(2)-1\big)!}&\text{if }2^k\leq n < 3\cdot 2^{k-1}\\ T(1)\frac{\big(k+S(3)-1\big)!}{\big(S(3)-1\big)!}&\text{if }3\cdot 2^{k-1}\leq n<2^{k+1} \end{array}\right\}\in\Theta(k!)=\Theta\big(\log_2(n)!\big).$$

Answer 2

First, lets rearrange the equation:

$$ T(2n) = T(n) \left ( 1 + \frac{T(n)}{T(n/2)} \right )$$

Then we substitute $n \to 2n$ to see:

$$ T(n) = T \left ( \frac{n}{2} \right ) \left ( 1 + \frac{T \left ( \frac{n}{2} \right )}{T(\frac{n}{4})} \right ) $$

Then, putting $n = 2^k$, and setting $S(k) = T(2^k)$, we see

$$ S(k) = S(k-1) \left ( 1 + \frac{S(k-1)}{S(k-2)} \right ) $$

Finally, $S(k) \in \Theta(k!)$, since

$$k! = (k-1)! \left (1 + \frac{(k-1)!}{(k-2)!} \right )$$

Thus $T(2^k) \in \Theta(k!)$, or equivalently, $T(n) \in \Theta((\log n)!)$

---

Hope this helps ^_^

Answer 3

Hint.

Calling

$$ G(n)=\frac{T(n)}{T(\frac n2)} $$

we have

$$ G(n) = G(2n)-1 $$

giving $G(n) = C_1 + \log_2 n$ then

$$ T(n) = (C_1+ \log_2 n)T\left(\frac n 2\right) $$

equivalent to

$$ \mathcal{T}(z) = \left( C_1 + z\right)\mathcal{T}(z-1) $$

with $z = \log_2 n$

giving

$$ \mathcal{T}(z) = C_2 \left(C_1+2\right)_{z-1} \ \ \text{(Pochhammer symbol)} $$

The conversion to $T(n)$ is left to the reader.