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.

I have some homework that I'm working on where there is a whole section of problems I need to solve taking the following form:

"Assume that T(1) = 1, and find the order of function T(n)."

I have no idea what this means, really, and I'm having difficulty finding anything specific enough online. What I've found (I think) is that a function of order k is a function that can be solved using the k previous terms of the sequence.

However, I don't really know how to apply this. An example of what I'm working with is as follows:

$$T(n) = 3T(\frac{n}{2}) + n$$

If someone could walk me through exactly what I need to do to find the order of this function, that would be great; I'm really lost.

Thanks in advance!

share|improve this question
1  
A lot of Master theorem type recurrences can be solved exactly. While this computes more information than what is required for the asymptotics I believe it does add to the understanding of what exactly is going on with these recurrences. There is one example here and another one here and here. –  Marko Riedel Jan 21 '13 at 22:28
    
@MarkoRiedel That's actually exactly what I needed -- the Master Theorem. I was able to get the information I needed with a simple Google search for it. Thanks! –  Benjamin Kovach Jan 21 '13 at 22:47
add comment

2 Answers 2

up vote 1 down vote accepted

We want to find $T(n)$ given the recurrence $$T(n) = 3T(n/2) + n$$ Let us write $n= 2^m$ and call $g(m) = T(2^m)$. We then have \begin{align} g(m) & = 3 g(m-1) + 2^m = 2^m + 3 (2^{m-1} + 3g(m-2)) = 2^m + 3 \cdot 2^{m-1} + 3^2 g(m-2)\\ & = 2^m + 3 \cdot 2^{m-1} + 3^2 \cdot 2^{m-2} + 3^3 g(m-3)\\ & = 2^m + 3 \cdot 2^{m-1} + 3^2 \cdot 2^{m-2} + 3^3 \cdot 2^{m-3} + 3^4 g(m-4) \end{align} Hence, using induction, you can prove that \begin{align} g(m) & = 2^m + \left(\dfrac32\right) \cdot 2^m + \left(\dfrac32\right)^2 \cdot 2^m + \cdots + \left(\dfrac32\right)^{m-1} \cdot 2^m + 3^m g(0)\\ & = 2^m \dfrac{(3/2)^m-1}{3/2-1} + 3^m g(0) = 2 \cdot (3^m-2^m) + 3^m g(0)\\ & = (g(0) + 2) 3^m - 2^{m+1} = (g(0) + 2) 3^{\log_2(n)} - 2n\\ & = (g(0) + 2) n^{\log_2(3)} - 2n\\ \end{align} Hence, $T(n)$ grows as $n^{\log_2(3)}$.

share|improve this answer
add comment

Perhaps it's the complexity in the sense of big O notation?

In your example,

$T(n) = 3T(n/2)+n$

$T(n) = 3(3T(n/2^2)+n/2)+n = 3^2T(n/2^2) + (3/2)n + n$

$T(n) = 3^2(3T(n/2^3) + n/2^2) + (3/2)n + n = 3^3T(n/2^3) + (3/2)^2n + (3/2)^1 +n$

After $k=\text{floor}(\log_2 n)$ times, you get

$T(n) =3^{k+1} T(O(1))+ n\sum_{i=0}^k({3\over2})^i =3^{k+1} T(O(1))+ n\sum_{i=0}^k({3\over2})^i =3^{k+1} T(O(1)) +n\frac{1.5^{k+1}-1}{1.5-1}$

So that $T(n)=\Theta(n 3^k)= \Theta(n 3^{\text{floor}(\log_2 n)})$.

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.