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

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

• – ryan Mar 5 at 0:01
• 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! – Raphael Mar 6 at 8:04

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

• Thank you this is an amazing answer and helps a lot! – Mandy Mar 5 at 23:45
• 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) ? – Mandy Mar 7 at 20:34
• You have to choose the same constant in both cases. That’s how induction works. – Yuval Filmus Mar 7 at 20:50

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.

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