1
$\begingroup$

Show $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n$ is $\in O(n)$.

I will make the bound to be $\in O(cn)$ instead.

Proof by strong induction.

  • Base case n =1

$T(1) = c$ and $cn=c*1=c$ $\checkmark$

  • Inductive Hypothesis : $T(k) \in O(ck)$ for $1\le k<n, n>1$.
  • Inductive Step: Prove for n. So prove that $T(n) \le O(ck)$.

Right away we can write $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n \\ \leq T(n/2)+T(n/4)+T(n/8) + n\\ = c(n/2)+c(n/4)+c(n/8)+n \ \ \ \ By \ Inductive \ Hypothesis$

$$= c(7n/8)+n \le cn+n ... $$ I am stuck here

*Goal: $\le cn - (some \ stuff)$ and some stuff needs to be $\ge 0$.

$\endgroup$
  • $\begingroup$ See: cs.stackexchange.com/a/83650/68251 $\endgroup$ – ryan Mar 5 at 0:01
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Mar 6 at 8:04
1
$\begingroup$

First, let me mention that $O(n)$ and $O(cn)$ are exactly the same thing. What you are really after is showing that $T(n) \leq cn$ for all $n$.

Let us aim at a slightly more relaxed goal: showing that $T(n) \leq An$ for some possibly larger constant $A$. For the base case, we need $A \geq c$. For the inductive step, we know that $$ T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n \leq A(n/2+n/4+n/8)+1 = (\tfrac{7}{8}A+1)n. $$ Recall that our goal is to deduce that $T(n) \leq An$. This would follow if $\tfrac{7}{8}A + 1 \leq A$, that is, if $A \geq 8$.

In total, if we take $A = \max(c,8)$ then both the base case and the inductive step go through.


As an aside, you can also use the Akra-Bazzi theorem to directly conclude that $T(n) = O(n)$.


Now let us try to obtain more insight on the recurrence. Let $S(n) = 8n - T(n)$. Then $$ S(n) = S(\lfloor n/2 \rfloor) + S(\lfloor n/4 \rfloor) + S(\lfloor n/8 \rfloor) + 8n - 8\lfloor n/2 \rfloor - 8\lfloor n/4 \rfloor - 8\lfloor n/8 \rfloor - n. $$ Since $8(n/a-1) < 8\lfloor n/a \rfloor \leq 8(n/a)$, we see that $$ S(n) = S(\lfloor n/2 \rfloor) + S(\lfloor n/4 \rfloor) + S(\lfloor n/8 \rfloor) + r(n), $$ where $0 \leq r(n) < 24$. Applying the Akra-Bazzi theorem, we get $S(n) = O(n^p)$ for some $p < 1$ (the solution to $(1/2)^p + (1/4)^p + (1/8)^p = 1$), and so $T(n) = 8n + O(n^p)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you this is an amazing answer and helps a lot! $\endgroup$ – Mandy Mar 5 at 23:45
  • $\begingroup$ So for base case we can choose either 8 or c (in this case c) , and for inductive step we can also choose 8 or c (in this case 8) ? $\endgroup$ – Mandy Mar 7 at 20:34
  • $\begingroup$ You have to choose the same constant in both cases. That’s how induction works. $\endgroup$ – Yuval Filmus Mar 7 at 20:50
1
$\begingroup$

It's very important that you understand what f(n) = O (g(n)) means. It means that there is a number $n_0 ≥ 0$ and a number c > 0 such that for every $n ≥ n_0$, f(n) ≤ c * g(n). It is a property of the whole function, not a property of some n. Saying "I prove by induction that for every n, f(n) = O (g(n))" doesn't make any sense at all. What makes sense is to say "I prove by induction that for every n ≥ n_0, f(n) ≤ c * g(n)".

So what you want to prove per induction using some suitable c, T(n) ≤ cn. One variant of complete induction uses an induction step where you proof "if the statement $S_k$ is true for every k < n, then $S_n$ is also true".

If T(k) ≤ ck is true for every k < n, then T(n) = T(n/2) + T(n/4) + T(n/8) + n ≤ cn/2 + cn/4 + cn/8 + n = (7/8 c + 1) n.

If c = 1 this means T(n) < 1 7/8 n. Not what we need, we need T(n) < cn. If c = 2 it means T(n) + 2 3/4 n. Slightly better but not good enough. For which c is (7/8 c + 1) n ≤ cn, or 7/8 c + 1 ≤ c? That's the case for c ≥ 8. The start of the induction is n=0, and it's easy to show that T(0) = 0.

So you haven't just shown that T(n) = O(n), you have shown the much stronger T(n) ≤ 8n.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you this is an excellent answer and helps me understand these kinds of problems in more depth! $\endgroup$ – Mandy Mar 5 at 23:46
  • $\begingroup$ You might have forgotten the base case. $\endgroup$ – Yuval Filmus Mar 6 at 16:38

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.