# Complexity of $T\left( n\right) =T\left( \dfrac{n}{3}\right) +T\left( \dfrac{2n}{3}\right) +\theta \left( 1 \right)$ without using master theorem

Calculate the complexity of $$T\left( n\right) =T\left( \dfrac{n}{3}\right) +T\left( \dfrac{2n}{3}\right) +\theta \left( 1 \right)$$

Without using the master theorem.

My take on this:

I found that the answer should be $$\theta \left( n \right)$$ but I have issues proving the upper bound (big O), even when using induction (the lower bound is quite easy to show using induction).

As I understand it, the total amount of work is the amount of nodes in the recursion tree, since the work on each node is $$\theta \left( 1 \right)$$.

But how many nodes are there? I tried using the fact that the height of the tree is $$\log _{1.5}{n}$$ and to bound it from above with the amount of nodes in a complete, perfectly balanced binary tree of height $$\log _{1.5}{n}$$, which is $$2^{\log _{1.5}\left( n\right) +1}-1$$, but I can't get $$O\left( n\right)$$ no matter what do I do, and I can’t think of a better bound.

Edit: I also saw this: How to solve the recurrence $T(n) = T(n/3) + T(2n/3)$? but didn't quite understand the answer, might not be something that we have covered

• Not a full answer, but was your reasoning that $T$ is linear something like this? Assume that $T(n) = an^b$, and let $c$ be the constant term behind $\theta(1)$. Then the recurrence relation becomes $$an^b = a\left(\frac{n}{3}\right)^b + a\left(\frac{2n}{3}\right)^b + c$$ $$3^b = 1 + 2^b + \frac{3^bc}{an^b}$$ As $n \to \infty$, that last term goes to 0, so we get $3^b = 1 + 2^b$, which has the solution $b = 1$. So $T$ is (asymptotically equal to) a first-degree polynomial.
– Dan
Commented Mar 31, 2023 at 22:58
• You can use the substitution method to show the complexity is at most $O(n)$. Let $T(n) = T(n / 3) + T(2n / 3) + q$ and assume $T(n) = kn - d$ for some constants $k,d$. Then, we substitute: $T(n) = T(n / 3) + T(2n / 3) + q = k\frac{n}{3} - d + k\frac{2n}{3} - d + q \leq kn - d$. The inequality holds when $d \geq q$. Commented Mar 31, 2023 at 23:09
• And so we conclude that $T(n) \leq kn - d$ for some constants $k,d$ which means $T(n) = O(n)$. Commented Mar 31, 2023 at 23:11

By using the substitution method one can show that the complexity of the recurrence relation you stated is $$O(n)$$. Let $$T(n) = T(n/3) + T(2n/3) + c$$ and assume $$T(n) \leq kn - d$$ for some constants $$k$$ and $$d$$, then by induction:
$$T(n) = k\frac{n}{3} - d + k\frac{2n}{3} - d + c$$
$$T(n) = kn - 2d + c \leq kn - d$$
The last inequality holds, if e.g. $$d \geq c$$. And so we conclude $$T(n) = O(n)$$. You did not provide a base case, so this case was not considered.