Running time recurrence relation, solving using induction

Question

I am having a hard time figuring out how to solve such problems, here is the one I am trying to solve:

T(n) = 1, if n = 1 T(n) = T(n/6) + 2T(n/3) + O(n), if n > 1

I need to show that T(n) is O(n) using induction.

I am thinking that my induction step might be wrong, I have done:

Base Case, n = 1 T(1) = 1, 1 is O(1)

Induction hypothesis: T(n) is O(n) Induction step: show T(2n) is O(2n)

But I just cant figure out what kind of algebra I need to do to get to a solution. Once I simplify the fractions as:

T(2n) = T(n/3) + 2T(2n/3) + O(n)

I just don't know what to do. Should I be using T(6n) or T(3n) maybe?

Thank you.

Answer 1

You could use the stronger version of the induction hypothesis which assumes the statement to be true for all values less than $n$, when proving the statement for $n$.

Answer 2

Let $T(1)\in O(1)$ and assume for some $n\geqslant 1$ that $T(k)\in O(n)$ for $1\leqslant k\leqslant n$. Then $$T(3n) = T(n) + 2T\left(\frac n3\right) + O(n), $$ so that $T(3n)\in O(n)$.