7
$\begingroup$

Using the recursion tree i tried solving this: $T(n)=T(n-1)+T(\frac{n}{2})+n$; the tree has two parts (branches) one that of $T(n-1)$ and other branch is of $T(\frac{n}{2})$. But as the term T(n-1) reach higher depth, I solved that part of the tree. Finally it resulted in O$(2^n)$ is it correct or is it $O(n^2)$? How can we solve it by substitution method?

$\endgroup$
  • $\begingroup$ If $T(n) = O(n^3)$, say $T(n)=Mn^3+...$, then the leading order of the right-hand side is $M(1+1/8)n^k$ - that is, $T(n)$ is defined to be a bit bigger than $Mn^k$. I think $T(n)$ grows faster than any polynomial. $\endgroup$ – Empy2 Oct 8 '13 at 13:03
  • $\begingroup$ The function $T(n)=-2n-2$ works. Also, if $U(n)=T(n)+2n+2$, then $U(n)=U(n-1)+U(n/2)$ without the final $n$. $\endgroup$ – Empy2 Oct 8 '13 at 13:06
9
$\begingroup$

If you want a final answer, skip to the last line.

$T(n) = T(n - 1) + T(n/2) + n$

The problem is at least $O(n^2)$. My guess is that the $T(n/2)$ contributes $log(n)$.

So let's check if $T(n) \in O(n^2 log(n))$

Does there exist $M$ such that as $n$ gets large:

$$\exists M>0, n_0, \forall n > n_0, T(n) \le M n^2 log(n) $$

Known: $T(n) = T(n - 1) + T(n/2) + n$

substitute known recursion into $T(n) \le M (n^2 log(n))$ :

$$T(n - 1) + T(n/2) + n \le M n^2 log(n)$$

$$T(n - 1) + T(n/2) \le M n^2 log(n) - n$$

We need 2 inductive hypothesis to check this, so we'll be using super violent strong induction:

$$\text{Inductive hypothesis:}$$ $$T(n - 1) \le M (n - 1)^2 log(n - 1)$$ $$T(n/2) \le M (n/2)^2 log(n/2)$$

We have inductive hypothesis of the forms $a < b$ and $c < d$ , we wish to use that to prove a statement of the form $a+c < e$, so we need to establish that $b+d < e$

$$M (n - 1)^2 log(n - 1) + M (n/2)^2 log(n/2) \le M n^2 log(n) - n$$

So we want to find if there is any $M$ that doesn't depend on $n$, that for a sufficiently large $n$, makes the above statement true.

$$M ((n - 1)^2 log(n - 1) + (n/2)^2 log(n/2) - n^2 log(n)) \le - n$$

$$M (n^2 log(n - 1) - 2nlog(n - 1) + log(n - 1) + 1/4n^2 log(n) - 1/4n^2log(2) - n^2 log(n)) \le -n$$

$$M (n^2 (log(n - 1) - 3/4 log(n) - 1/4log(2)) - 2nlog(n - 1) + log(n - 1) ) \le -n$$

The coefficient of $n^2$ is $log(n - 1) - 3/4 log(n) - 1/4log(2)$, which you can see by inspection will be positive for sufficiently large $n$. Unfortunately, since $M$ must be positive, and the right hand side is negative, that means that no value of $M$ will make the equation true for sufficiently large $n$.

Therefore we cannot conclude that $T(n) \in O(n^2 log(n))$. One step in the above was an implication rather than an equivalence, so we can't necessarily say that it is false either. We'll check another bound.


Let's see if any polynomial satisfies this. Is $T(n) \in O(n^c)$ for some c.

$$T(n) \le M n^c$$

Known: $T(n) = T(n - 1) + T(n/2) + n$

substitute known recursion into $T(n) \le M n^c$ :

$$T(n - 1) + T(n/2) + n \le M n^c$$

$$T(n - 1) + T(n/2) \le M n^c - n$$

2 inductive hypothesis again: $$T(n - 1) \le M (n - 1)^c$$ $$ T(n/2) \le M (n/2)^c$$

We have inductive hypothesis of the forms $a < b$ and $c < d$ , we wish to use that to prove a statement of the form $a+c < e$, so we need to establish that $b+d < e$

$$M (n - 1)^c + M (n/2)^2 \le M n^c - n$$

So we want to find if $\exists M, \forall n > n_0, \text {above statement holds}$. Let's ignore all polynomial terms of degree less than $c$, since we are only concerned with $n$ above a threshhold.

$$M ((n - 1)^c + (n/2)^c - n^c) \le - n$$

$$M (n^c + \frac{1}{2^c} n^c - n^c + \dots) \le -n$$

$$M \frac{1}{2^c} n^c + \dots \le -n$$

So we can't find any polynomial which seems to solve this.


I think someone suggested checking if $T(n) \in O(n^{log(n)})$. That would be an interesting result.

$$T(n) \le M n^{log(n)}$$

Known: $T(n) = T(n - 1) + T(n/2) + n$

substitute known recursion into $T(n) \le M n^{log(n)}$ :

$$T(n - 1) + T(n/2) + n \le M n^{log(n)}$$

$$T(n - 1) + T(n/2) \le M n^{log(n)} - n$$

2 inductive hypothesis again: $$ T(n - 1) \le M (n - 1)^{log(n - 1)}$$ $$ T(n/2) \le M (n/2)^{log(n / 2)}$$

...blah blah blah

$$M (n - 1)^{log(n - 1)} + M (n/2)^{log(n / 2)} \le M n^{log(n)} - n$$

$$M ((n - 1)^{log(n - 1)} + (n/2)^{log(n / 2)} - n^{log(n)}) \le - n$$

$$M (n^{log(n)} - (n - 1)^{log(n - 1)} - (n/2)^{log(n / 2)}) \ge n$$

At this point it's pretty obvious that we've found a solution. Yay. Try $M=1$.

$$n^{log(n)} - (n - 1)^{log(n - 1)} - (n/2)^{log(n / 2)} \ge n$$

This holds for $n > 5.4$, a witness for $n_0$.

Therefore we can conclude that $T(n) \in O(n^{log(n)})$.

We can all be happy now. Please double check this for typos.

$\endgroup$
  • $\begingroup$ A nice bit of work! There are three equations in a row beginning with $M$; the sign of the right-hand side changes going from the first to the second row. Could you check that? $\endgroup$ – Empy2 Oct 8 '13 at 12:59
  • $\begingroup$ You are right, I'm going to see what I can do to fix it now. I have to check a larger O() bound. Sad. Oh well I'll leave the first part in and change up the second. $\endgroup$ – DanielV Oct 8 '13 at 13:19
  • $\begingroup$ @Michael thanks for your observation, I believe I have established $O(n^{log(n)})$ as you suggested above. $\endgroup$ – DanielV Oct 8 '13 at 14:07
  • $\begingroup$ CLRS (3/e, problem 4.4-5) missed "starring" this problem to indicate this is a tough one. This is a much harder problem than many of the others they have starred. $\endgroup$ – arun Apr 24 '15 at 3:51
  • $\begingroup$ What about a matching lower bound? $\endgroup$ – Yuval Filmus Sep 13 '15 at 21:30
3
$\begingroup$

Following up on Michael's answer, let $S(n) = T(n) + 2n + 2$. Calculation shows that $$ S(n) = S(n-1) + S(n/2). $$ (This is assuming that by $n/2$ you actually mean $n/2$ rather than $\lfloor n/2 \rfloor$ or the like.) Mahler showed that every function satisfying the very similar functional equation $S(n+1) = S(n) + S(n/2)$ has the asymptotic form $$ S(n) = \Theta\left( \sum_{m=0}^\infty 2^{-m(m-1)/2} \frac{n^m}{m!} \right) . $$ A function satisfying our functional equation probably has the very same asymptotic form. Stirling's approximation gives $$ 2^{-m(m-1)/2} \frac{n^m}{m!} \sim \frac{n^m}{\sqrt{2\pi m}(m/e)^m \sqrt{2}^{m(m-1)}}. $$ Taking logarithm of the $m$th term, we get roughly $$ m\log n - \Theta(m^2). $$ This is maximized for $\log n = \Theta(m)$, at which case the value of the logarithm is $\Theta(\log^2 n)$. We deduce that the sum itself is roughly $$ \exp \Theta(\log^2 n) = n^{\Theta(\log n)}. $$ Therefore (modulo some inaccuracies), $$ T(n) = n^{\Theta(\log n)}. $$

$\endgroup$
1
$\begingroup$

I asked a similar question earlier this year, and found a technical paper on it from 1948. Even without the extra $+n$ at the end, the formula was pretty cool.

how many ways to make change, asymptotics

For this problem, without the floor function, try $T(n)=an+b$, and solve for $a$ and $b$.

$\endgroup$
  • $\begingroup$ So, is this the solution is O(2^n)? I still have a confusion with the solution. $\endgroup$ – studnt Oct 8 '13 at 11:33
  • $\begingroup$ I think there is one particular solution that is linear. But most of the solutions, if I read the formula correctly, are $O(n^{\log n})$ $\endgroup$ – Empy2 Oct 8 '13 at 11:43
0
$\begingroup$

Sorry Dear Yuval Filmus, you right and I got it. I edited my wrong, thanks. I think we can look at it this way:

$T(n)=2T(n/2)+n < T(n)=T(n−1)+T(n/2)+n < T(n)=2T(n−1)+n$

Now it is very clear that we have:

$Θ(n*\log n) < Θ(T(n)) < Θ(2^n)$

And finally your solution is righ. But it will take a lot of range of functions. Is there any idea how to reduce this range? I have a few ways, but I'm not sure. For now I just guess:

Θ(T(n)) = Θ( 2^(log (logn)))

This can be true?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.