2
$\begingroup$

The questions is to find the running time $T(n)$ of the following function:

$$T(n)=3\cdot T(n/2) + n \tag{1}$$

I know how to solve it using Master theorem for Divide and Conquer but I am trying to solve it by expanding: $$\textstyle T(n) = n+\frac{3}{2}n +(\frac{3}{2})^2n + (\frac{3}{2})^3n + \cdots \tag{2}$$ which implies $$T(n)=n\sum_{k=1}^{n}({\textstyle \frac{3}{2}})^{k-1} \tag{3}$$ and so $$T(n)=2n\cdot(({\textstyle\frac{3}{2}})^n-1) \tag{4}$$

The right answer to this problem is $\Theta(n^{\log3})$. How can I reach to right answer through my approach as shown above.Is my approach wrong ? How can I solve it without using Master theorem.

Any help is appreciated.

$\endgroup$
2
$\begingroup$

Your approach is almost correct, except for the fact that the upper limit of your summation should be $\log_2n$, rather than $n$. You should have $$ T(n)=3^kT\left(\frac{n}{2^k}\right)+\left[n\left(\frac{3}{2}\right)^{k-1}+n\left(\frac{3}{2}\right)^{k-2}+\dotsm+n\left(\frac{3}{2}\right)^0\right] $$ and your goal is to drive $n/2^k$ down to a value that will allow you to replace $T(n/2^k)$ with to a value you know, like, say, $T(1)$. That will happen when $n=2^k$ so $k=\log_2n$. Using that value for $n$ gives you $$\begin{align} T(n)&=3^{\log_2n}T(1)+n\sum_{j=1}^{\log_2n}\left(\frac{3}{2}\right)^{j-1}\\ &=3^{\log_2n}T(1)+2n\left[\left(\frac{3}{2}\right)^{\log_2n}-1\right]\\ &=n^{log_23}T(1)+2n[n^{\log_2(3/2)}-1]\\ &= n^{\log_23}T(1)+n^{log_23}-2n\\ &= \Theta(n^{\log_23}) \end{align}$$

$\endgroup$
  • $\begingroup$ Sorry ! I mistaken while writing..now edited the post. $\endgroup$ – Aditya pratap singh Jul 10 '16 at 17:34
2
$\begingroup$

You have a mistake going from (2) to (3) because you lost $n$ and it is not clear why your sum should range from $i = 1$ to $i = n$ (it does not). Then it is not clear how you got from (3) to (4) where $n$ reappeared. Perhaps you just los $n$ in (3) but otherwise you had it on paper.

Let us try again: \begin{align*} T(n) &= n + (3/2) n + (3/2)^2 n + \cdots \end{align*} But when does sum end? (This is what created your mistake.) It ends when we get to the base case, which is $T(1)$. After $k$ unfoldings we have $T(n/2^k)$ so we will reach $T(1)$ when $k = \log_2 n$. Thus, we continue like this: \begin{align*} T(n) &= n + (3/2) n + (3/2)^2 n + \cdots + (3/2)^{\log_2 n} T(1) \\ &= \textstyle \sum_{i=0}^{\log_2 n} (3/2)^i n\\ &= n \cdot \textstyle \sum_{i=0}^{\log_2 n} (3/2)^i. \end{align*} It remains to add the sum. It is a geometric series, so we can look up the formula $\sum_{i=0}^k a^i = (a^{k+1} - 1)/(a - 1)$ and get \begin{align*} {\textstyle \sum_{i=0}^{\log_2 n} (3/2)^i} &= \frac{(3/2)^{1 +\log_2 n} - 1}{3/2 - 1} \\ &= 2 \cdot ((3/2) \cdot (3/2)^{\log_2 n} - 1) \\ &= 3 \cdot (3/2)^{\log_2 n} - 2 \\ &= 3 \cdot (n^{\log_2 (3/2)}) - 2 \\ &\in \Theta(n^{\log_2 (3/2)}) \approx \Theta(n^{0.58}) \end{align*} The final result is this sum multiplied with $n$, so it is $$\Theta(n \cdot n^{\log_2(3/2)}) = \Theta(n^{\log_2 2 + \log_2 (3/2)}) = \Theta(n^{\log_2 3}),$$ assuming I can still do logarithms....

$\endgroup$
2
$\begingroup$

You are correct that $$ \begin{align*} T(n) &= n + \tfrac{3}{2} n + (\tfrac{3}{2})^2 n + \cdots + (\tfrac{3}{2})^{k-1} n + 3^k T(n/2^k) \\ &= n \sum_{t=0}^{k-1} (\tfrac{3}{2})^t + 3^k T(n/2^k) \\ &= 2[(\tfrac{3}{2})^k-1]n + 3^k T(n/2^k). \end{align*} $$ Let's assume that $n$ is a power of $2$, and the base case is $T(1) = C$. In order to reach the base case, we need to choose $k$ so that $n = 2^k$. In other words, we need to take $k = \log_2 n$. We then have $3^k = n^{\log_2 3}$ and $(3/2)^k = n^{\log_2 3 - 1}$. Substituting these values, we find out that $$ T(n) = 2[n^{\log_2 3-1}-1]n + Cn^{\log_2 3} = (C+2)n^{\log_2 3} - 2n. $$ This shows the stronger result $$ T(n) \sim (C+2) n^{\log_2 3}, $$ which implies $T(n) = \Theta(n^{\log_2 3})$.

$\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.