4
$\begingroup$

Solve the recurrence relation: $T(n)=T(n/4)+T(3n/4)+n$. Also, specify an asymptotic bound.

Clearly $T(n)\in \Omega(n)$ because of the constant factor. The recursive nature hints at a possibly logarithmic runtime (because $T(n) = T(n/2) + 1$ is logarithmic, something similar may occur for the problem here). However, I'm not sure how to proceed from here.

Even though the recurrence does not specify an initial value (i.e. $T(0)$), if I set $T(0) = 1$ some resulting values are:

  0     1
100   831
200  1939
300  3060
400  4291
500  5577
600  6926
700  8257
800  9665
900 10933

The question: Is there a technique that I can use to solve the recurrence in terms of $n$ and $T(0)$? If that proves infeasible, is there a way to determine the asymptotic behavior of the recurrence?

$\endgroup$
2
  • 1
    $\begingroup$ Hint: try $T(n) = c n \log n$ for appropriate constant $c$. $\endgroup$ – Robert Israel Oct 18 '12 at 0:49
  • $\begingroup$ @Robert Israel: Your trying can find the particular solution part of the recurrence relation. $\endgroup$ – doraemonpaul Aug 12 '13 at 5:03
5
$\begingroup$

This calls for the use of the Akra-Bazzi Method. Given that $T(n) = T(n/4) + T(3n/4) +n$, we have that
\begin{align} g(n)= n,\\ a_1 = 1, a_2 = 1 ~\mbox{and}\\ b_1= 1/4, b_2 = 3/4 \end{align}

We first need to solve for $p$ subject to $(1/4)^p + (3/4)^p = 1$ , giving $p= 1$.The method now gives $T(x) \in \Theta(f(x))$, where

\begin{align} f(x) = x^p (1+ \int _{[1,x]} \frac{g(u)}{u^{1+p}} du) \\ = x(1+ \log(x)) \end{align}

Thus $T(n) = \Theta(n \log(n))$.

$\endgroup$
1
  • $\begingroup$ That's really nice. I hadn't heard of that result. Thanks. $\endgroup$ – marty cohen Oct 18 '12 at 1:42
1
$\begingroup$

$T(n)=T\left(\dfrac{n}{4}\right)+T\left(\dfrac{3n}{4}\right)+n$

$T(n)-T\left(\dfrac{n}{4}\right)-T\left(\dfrac{3n}{4}\right)=n$

For the particular solution part, getting the close-form solution is not a great problem.

Let $T_p(n)=An\ln n$ ,

Then $An\ln n-\dfrac{An}{4}\ln\dfrac{n}{4}-\dfrac{3An}{4}\ln\dfrac{3n}{4}\equiv n$

$An\ln n-\dfrac{An}{4}(\ln n-\ln4)-\dfrac{3An}{4}(\ln n+\ln3-\ln4)\equiv n$

$\dfrac{(4\ln4-3\ln3)An}{4}\equiv n$

$\therefore\dfrac{(4\ln4-3\ln3)A}{4}=1$

$A=\dfrac{4}{4\ln4-3\ln3}$

$\therefore T_p(n)=\dfrac{4n\ln n}{4\ln4-3\ln3}$

But getting the complementary solution part is not optimistic.

Since we should handle the equation $T_c(n)-T_c\left(\dfrac{n}{4}\right)-T_c\left(\dfrac{3n}{4}\right)=0$ .

$\endgroup$
1
  • 1
    $\begingroup$ Why resurrect this (answered) question from 2+ years ago? $\endgroup$ – Did Jan 18 '15 at 11:49

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.