1

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

GreekMustard
  • 147
  • 8
  • 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 Mar 31 '23 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$. – prcssngnr Mar 31 '23 at 23:09
  • And so we conclude that $T(n) \leq kn - d$ for some constants $k,d$ which means $T(n) = O(n)$. – prcssngnr Mar 31 '23 at 23:11

1 Answers1

1

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.

Harish Chandra Rajpoot
  • 37,450
prcssngnr
  • 1,191