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

Question

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$.

Answer 1

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)$.

Answer 2

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.