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

  • $\begingroup$ See: cs.stackexchange.com/a/83650/68251 $\endgroup$
    – ryan
    Mar 5, 2020 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, 2020 at 8:04

2 Answers 2


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

  • $\begingroup$ Thank you this is an amazing answer and helps a lot! $\endgroup$
    – Mandy
    Mar 5, 2020 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, 2020 at 20:34
  • $\begingroup$ You have to choose the same constant in both cases. That’s how induction works. $\endgroup$ Mar 7, 2020 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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