Inductive Proof that a recurrence isn't O(n) by showing it is Omega(nlogn)

Question

Note: This is related to homework.

I am attempting to show that T(n/3) + T(2n/3) + n >= cn , for all c > 0.

When I attempted this, the base case failed (T(1) = 1 >= cn, for all c > 0, is not true). So to work around this, I thought to show that the problem has a lower bound which is higher than O(n). Does this constitute a correct proof?

Answer 1

As a hint, try adding in more terms. Suppose that your function satisfies

T(n) ≥ k₁n log n + k₂n + k₃

Now, when you plug in n = 1, the right-hand side can be made nonzero by setting k₂ and k₃ appropriately. This sort of technique is common for using induction to upper-bound and lower-bound functions and works because those lower-order terms are irrelevant for big-O notation and handle the smaller cases gracefully.