1
$\begingroup$

Hi all I'm preparing for a midterm and the following appeared as a practice problem that I'm not quite sure how to solve. It asks to find a tight bound on the recurrence using induction

$$ {\rm T}\left(n\right) ={\rm T}\left(\left\lfloor{n \over 2}\right\rfloor\right) +{\rm T}\left(\left\lfloor{n \over 4}\right\rfloor\right) +{\rm T}\left(\left\lfloor{n \over 8}\right\rfloor\right) +n $$

I'm aware a similar question has been asked here before, but that thread dates back to a year or so ago and I never really understood the rationale behind the answer given (see here: Need some help with this recurrence equation). My guess is that it is in $\Theta(n)$, but I'm not sure how to get a more precise relation than that. I've tried expanding out the recurrence a bit, but I'm not seeing any obvious pattern.

$\endgroup$
  • $\begingroup$ Do you mean $$ T(n)=T(\lfloor{\frac{n}{2}}\rfloor)+T(\lfloor{\frac{n}{4}}\rfloor)+T(\lfloor{ \frac{n}{8} }\rfloor)+n? $$ $\endgroup$ – Omnomnomnom Mar 17 '14 at 4:03
  • $\begingroup$ Indeed I did. My apologies $\endgroup$ – user979616 Mar 17 '14 at 4:05
  • $\begingroup$ While I'm at it (now I'm just being picky), rational is an adjective (unless you mean a number), rationale is the noun you're looking for. $\endgroup$ – Omnomnomnom Mar 17 '14 at 4:06
  • $\begingroup$ haha thank you. I found the two answers given to this question came to the same conclusion, but were totally different in their approaches and I felt a tad mathematically complex for something which I wasn't expecting to be terribly difficult. $\endgroup$ – user979616 Mar 17 '14 at 4:14
  • $\begingroup$ Neither of them used induction, either. Honestly, I'm not sure what exactly they're going for. $\endgroup$ – Omnomnomnom Mar 17 '14 at 4:20
1
$\begingroup$

The solution is cleary increasing. Use the change of variables $n = 2^k$ and $T(2^k) = a_k$, so that:

$$ a_k = a_{k - 1} + a_{k - 2} + a_{k - 3} + 2^k $$

This is the same as:

$$ a_{k + 3} = a_{k + 2} + a_{k + 1} + a_k + 8 \cdot 2^k $$

Define $A(z) = \sum_{k \ge 0} a_k z^k$, multiply the recurrence by $z^k$ and sum over $k \ge 0$ to get, after recognizing some sums:

$$ \frac{A(z) - a_0 - a_1 z - a_2 z^2}{z^3} = \frac{A(z) - a_0 - a_1 z}{z^2} + \frac{A(z) - a_0}{z} + A(z) + 8 \cdot \frac{1}{1 - 2 z} $$

Set $a_0 = a_1 = a_2 = 1$ so that:

$$ A(z) = \frac{1 - 2 z - 2^2 + 10 z^3}{(1 - 2 z) (1 - z - z^2 - z^3)} $$

By Descarte's rules of signs, $p(z) = 1 - z - z^2 - z^3$ has at most one positive zero, and we know $p(0) = 1$ and $p(1) = -2$ (the positive root is 0.543689, but in any case it is less than 1). Considering $p(-z) = 1 + z - z^2 + z^3$, again by the same rule there are at most 2 negative zeros. But we can write:

$$ p(z) = 1 - \frac{z (z^3 - 1)}{z - 1} $$

For negative $z$, the second term is positive, there are no negative zeros.

A simple bound on the zeros of $a_0 + \dotsb + a_n z^n$ is that they are in the circle of radius $\rho$ around the origin, where:

$$ \rho = \min\left\{ n \left\lvert \frac{a_0}{a_1} \right\rvert, \sqrt[n]{\left\lvert \frac{a_0}{a_n} \right\rvert} \right\} $$

This gives $\rho = 1$ in our case. By Bender's theorem (Bender, "Asymptotic Methods in Enumeration", SIAM Review 16:4 (oct 1974), pp 485-515), which states that if $A(z) = \sum_{n \ge 0} a_n z^n, B(z) = \sum_{n \ge 0} b_n z^n$, with convergence radii $\alpha \ge \beta > 0$, $C(z) = A(z) \cdot B(z) = \sum_{n \ge 0} c_n z^n$, with $\lim_{n \to \infty} \frac{b_{n - 1}}{b_n} = b$, $A(b) \ne 0$ then $c_n \sim A(b) b_n$.

The limit $b = 1/2$, so the theorem tells us that:

$$ a_k \sim 8 \cdot 2^k $$

Translating back, $T(n) \sim 8 n$

$\endgroup$
4
$\begingroup$

Inductive step: assume $T(k) \leq Ck$ for all $k<n$. We then have $$ \begin{align} T(n) &= T\left(\left\lfloor{n \over 2}\right\rfloor\right) +T\left(\left\lfloor{n \over 4}\right\rfloor\right) +T\left(\left\lfloor{n \over 8}\right\rfloor\right) +n\\ & \leq C\left(\left\lfloor{n \over 2}\right\rfloor\right) +C\left(\left\lfloor{n \over 4}\right\rfloor\right) +C\left(\left\lfloor{n \over 8}\right\rfloor\right) +n\\ & \leq C\left({n \over 2}\right) +C\left({n \over 4}\right) +C\left({n \over 8}\right) +n\\ &= \frac{7}{8}C\,n + n = \left(\frac{7}{8} C + 1\right)n \leq Cn \end{align} $$ In order for this to work, we'd need $C \geq 8$. In fact, we can get it to work with $C = 8$. Just note (for the base case) that $$ T(0) = 3T(0) + 0 \implies T(0) = 0 $$ So that we have $T(0) \leq 8\cdot 0$. Great, there's our upper bound! That is, we have shown that $T(n) \leq 8n$, so that $$ T(n) = O(n) $$ Now, we need to show that $T(n) \geq cn$ for some $c$. Clearly, though, $T(n) \geq n$.

$\endgroup$
  • $\begingroup$ This makes so much more sense. Thank you. I think reading the previous post just confused me. $\endgroup$ – user979616 Mar 17 '14 at 4:39
0
$\begingroup$

Take k = max{8, T(1)} and you can easily show by induction that T(n) is no greater than kn. The lower bound is trivial.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.