Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Well I got this problem:

$$T(0) = 0$$ $$T(n) = 3T(n/2) + n, n \geq 1$$

I simplified the equation to the following.

$$3^iT(n/2^i) + 2n((3/2)^i - 1)$$

From this point I am confused how to solve. Thanks for any help.

share|improve this question
    
How did you simplify this formula? –  Mhenni Benghorbal Aug 28 '13 at 6:04
    
Might be useful: link –  TZakrevskiy Aug 28 '13 at 6:43
add comment

2 Answers

Since $n$ is integer, what is $T(n)$ when $n == 1$?

Other than that, let $n = 2^m$ we have,

$$ T(2^m) = 3T(2^{m-1}) + 2^m, m \ge 0 $$

Let $f(m) = T(2^m)$,

$$ f(m) = 3f(m-1) + 2^m $$

=>

$$ f(m) + 2^{m+1} = 3(f(m-1) + 2^m) $$

If you can solve $$g(m) = f(m) + 2^{m+1} = 3g(m)$$ you will got the idea.

It looks like a high school math question though.

share|improve this answer
add comment

I claim that $\boxed{T(n) = \Theta(n^{\log_2 3})}$. This magical claim came from Case 1 of the Master Method. To see this, I will prove it by induction (I'll skip the base case).

Induction Hypothesis: Assume that there exist some $a,b,c,d>0$ such that for all $k<n$, we have: $$ ak^{\log_2 3} + bk \leq T(k) \leq ck^{\log_2 3} - dk $$

It remains to prove that the inequality holds true for $k=n$. Observe that: \begin{array}{rcccl} 3T(n/2) + n &=& T(n) &=& 3T(n/2) + n \\ 3\left[a\left(\dfrac{n}{2}\right)^{\log_2 3} + b\left(\dfrac{n}{2}\right)\right] + n &\leq& T(n) &\leq& 3\left[c\left(\dfrac{n}{2}\right)^{\log_2 3} - d\left(\dfrac{n}{2}\right) \right] + n\\ 3\left[a\left(\dfrac{n^{\log_2 3}}{3}\right) + \left(\dfrac{b}{2}\right)n\right] + n &\leq& T(n) &\leq& 3\left[c\left(\dfrac{n^{\log_2 3}}{3}\right) - \left(\dfrac{d}{2}\right)n \right] + n\\ \left[an^{\log_2 3} + \left(\dfrac{3b}{2}\right)n\right] + n &\leq& T(n) &\leq& \left[cn^{\log_2 3} - \left(\dfrac{3d}{2}\right)n \right] + n\\ \left[an^{\log_2 3} + bn\right] + \left(\dfrac{b}{2} + 1 \right)n &\leq& T(n) &\leq& \left[cn^{\log_2 3} - dn \right] + \left(1-\dfrac{d}{2}\right)n\\ an^{\log_2 3} + bn &\leq& T(n) &\leq& cn^{\log_2 3} - dn\\ \end{array} provided that $d \geq 2$. This completes the induction.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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