$\Theta$-notation of the recurrences $T(n) = 3T(n/2 +1) + n$ and $T(n) = 4T(n/2)-4T(n/4)+1$

Question

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

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

I am really stuck on these two recurrences and finding out their answers in $\Theta$-notation.

For a) I have tried writing it as one fraction and trying to write the recurrence in terms of $K$ but I can't seem to find the right pattern and I have tried somehow using master's theorem but don't know how I could apply it.

For b) I have tried the substitution $k=n/2$, writing $T(n/4)$ in terms of $T(n/2)$ and trying to solve it that way to find a series to simplify somehow but I just don't seem to be getting it.

Answer 1

Both of these recurrences can be solved using the Akra-Bazzi Method. In both cases you should check that all the assumptions are satisfied.

Now for problem (a) we need to solve $3 \cdot \left ( \frac{1}{2} \right )^p = 1$, so that $p = \log_2(3)$. Then Akra-Bazzi promises that

$$ \begin{align} T(x) &= \Theta \left ( x^p \cdot \left ( 1 + \int_1^x \frac{u}{u^{1+p}} \ du \right ) \right ) \\ &= \Theta \left ( x^p \cdot \left ( 1 + \frac{x^{1-p}}{1-p} \right ) \right ) \\ &= \Theta \left ( x^p \right ) \\ &= \Theta \left ( x^{\log_2(3)} \right ) \end{align} $$

and this agrees with wolframalpha. Note we could have also heuristically done this computation by guessing that $\frac{n}{2} + 1 \approx \frac{n}{2}$, and then using simpler techniques, such as the tree method or the master theorem.

---

For problem (b) we'll use a common trick: Write $n = 2^k$. The the relation becomes

$$S(k) = 4S(k-1) - 4S(k-2) + 1$$

which is "just" a linear recurrence, which we can solve by any number of standard techniques, such as generating functions. For us, we see that $S(k) = \Theta \left ( k 2^k \right )$, which (remembering $n = 2^k$ so that $k = \log_2(n)$) gives us $T(n) = \Theta(n \log n)$. This, again, agrees with wolframalpha.

---

I hope this helps ^_^

Answer 2

Regarding the recurrence

$$ T(n) = a T\left(\frac nb+1\right)+cn $$

with $a\ne 1, b\gt 0, b\ne 1, a\ne b$ we have that a particular solution is given by

$T_p(n) = c_0 + c_1 n$ because after substitution we have

$$ c_0 + c_1 n = a\left(\frac{c_0+c_1n}{b}\right)+c(c_0+c_1 n) $$

and thus

$$ T_p(n) = \frac{a b c}{(a-1) (a-b)}-\frac{b c}{a-b} n $$

For the homogeneous

$$ T_h(n) = a T_h\left(\frac nb+1\right) $$

Using the ansatz $T_h(n) = a^{\alpha(n)}$ after substitution we have

$$ a^{\alpha(n)} = a\cdot a^{\alpha\left(\frac nb+1\right)} $$

so we follow with

$$ \alpha(n) = \alpha\left(\frac nb+1\right)+1 $$

to solve this recurrence we use the ansatz $\alpha(n) = \log_b\left(d_0+d_1 n\right)$ then substituting

$$ \log_b\left(d_0+d_1 n\right) = \log_b\left(d_0+d_1 \left(\frac nb+1\right)\right)+1=\log_b\left(b d_0+d_1 b + n d_1\right) - 1 + 1 $$

then from $d_0 = b d_0+d_1 b$ we have

$$ \alpha(n) = \log_b\left(-d_o\left(\frac{b-1}{b}n-1\right)\right)= c_3 + \log_b\left(\frac{b-1}{b}n-1\right) $$

so

$$ T_h(n) = a^{c_3 + \log_b\left(\frac{b-1}{b}n-1\right)} $$

then

$$ T(n) = a^{c_3 + \log_b\left(\frac{b-1}{b}n-1\right)}+\frac{a b c}{(a-1) (a-b)}-\frac{b c}{a-b} n $$

NOTE

Here with $c_3 = 0$ happens that $a^{\log_b\left(\frac{b-1}{b}n-1\right)}$ obeys the homogeneous also then it can be included into the particular, thus

$$ T_p(n) = \frac{a b c}{(a-1) (a-b)}-\frac{b c}{a-b} n + a^{\log_b\left(\frac{b-1}{b}n-1\right)} $$

and

$$ T(n) = c_4a^{\log_b\left(\frac{b-1}{b}n-1\right)}+\frac{a b c}{(a-1) (a-b)}-\frac{b c}{a-b} n + a^{\log_b\left(\frac{b-1}{b}n-1\right)} $$