patternMinor
The recursion $T(n) = T(n/2)+T(n/3)+n$
Viewed 0 times
therecursionstackoverflow
Problem
I'm looking at the reccurrence
$$T(n) = T(n/2) + T(n/3) + n,$$
which describes the running time of some unspecified algorithm (base cases are not supplied).
Using induction, I found that $T(n) = O(n\log n)$, but have been told that this is not tight. Indeed, assume inductively that $T(k) \leq Ck\log k$ for all $k 0$, and so the last expression is dominated by $C\frac{5}{6}n\log n\leq Cn\log n$.
My first question is, what is a tighter bound that this?
Second, I tried to use the Akra-Bazzi method to solve this, so let $p$ solve
$$\left(\frac{1}{2}\right)^p + \left(\frac{1}{3}\right)^p = 1.$$
Then approximately $p=0.79$, and (with $g(n) = n$) I get
$$\int_1^n \frac{g(u)}{u^{p+1}} du = \int_1^n \frac{1}{u^{p}} du = \frac{1}{1-p}(n^{1-p}-1),$$
and so
$$T(n) = \Theta\left(n^p\left(1+\frac{1}{1-p}(n^{1-p}-1)\right)\right).$$
This equals $\Theta(n^p + \frac{1}{1-p}n-\frac{1}{1-p}n^p)$, so overall $\Theta(n)$, since $p<1$. My second question is that I don't really believe that $T$ is linear, so what went wrong in my application of Akra-Bazzi?
Best regards.
$$T(n) = T(n/2) + T(n/3) + n,$$
which describes the running time of some unspecified algorithm (base cases are not supplied).
Using induction, I found that $T(n) = O(n\log n)$, but have been told that this is not tight. Indeed, assume inductively that $T(k) \leq Ck\log k$ for all $k 0$, and so the last expression is dominated by $C\frac{5}{6}n\log n\leq Cn\log n$.
My first question is, what is a tighter bound that this?
Second, I tried to use the Akra-Bazzi method to solve this, so let $p$ solve
$$\left(\frac{1}{2}\right)^p + \left(\frac{1}{3}\right)^p = 1.$$
Then approximately $p=0.79$, and (with $g(n) = n$) I get
$$\int_1^n \frac{g(u)}{u^{p+1}} du = \int_1^n \frac{1}{u^{p}} du = \frac{1}{1-p}(n^{1-p}-1),$$
and so
$$T(n) = \Theta\left(n^p\left(1+\frac{1}{1-p}(n^{1-p}-1)\right)\right).$$
This equals $\Theta(n^p + \frac{1}{1-p}n-\frac{1}{1-p}n^p)$, so overall $\Theta(n)$, since $p<1$. My second question is that I don't really believe that $T$ is linear, so what went wrong in my application of Akra-Bazzi?
Best regards.
Solution
If $T(1)\le 6$ and $T(2)\le 12$, we can show that $T(n)\le 6n$ by induction.
$$T(n) = T(n/2) + T(n/3) + n \le 6(n/2)+ 6(n/3)+n= 6n.$$
More generally, let $c\gt6$ be a constant such that $T(1)\le c$ and $T(2)\le 2c$, then we can prove routinely that $T(n)\le cn$. Although it might seem unbelievable to you, it is true that
$$T(n)=O(n).$$
Intuitively, since $\dfrac12+\dfrac13\lt1$, the terms $T(n/2)$ and $T(n/3)$ is not big enough to lift $n$ to a power of $n$ of a larger exponent.
There is nothing wrong in your application of Akra-Bazzi method, which tells us that $T(n)=\Theta(n)$.
$$T(n) = T(n/2) + T(n/3) + n \le 6(n/2)+ 6(n/3)+n= 6n.$$
More generally, let $c\gt6$ be a constant such that $T(1)\le c$ and $T(2)\le 2c$, then we can prove routinely that $T(n)\le cn$. Although it might seem unbelievable to you, it is true that
$$T(n)=O(n).$$
Intuitively, since $\dfrac12+\dfrac13\lt1$, the terms $T(n/2)$ and $T(n/3)$ is not big enough to lift $n$ to a power of $n$ of a larger exponent.
There is nothing wrong in your application of Akra-Bazzi method, which tells us that $T(n)=\Theta(n)$.
Context
StackExchange Computer Science Q#104688, answer score: 6
Revisions (0)
No revisions yet.