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.

We are studying about recurrences in our analysis of algorithms class. As an example of the substitution method (with induction) we are given the following: $$T(n) = \lbrace 2T\left(\frac{n}{2}\right) + n \quad\text{if}\quad n > 1\rbrace$$

First step in the substitution method: "Guess: $n \lg n + n$"

Second step: "Inductive step - Inductive hypothesis is that $T(k) = k \lg k + k$ for all $k < n$. We'll use this inductive hypothesis for $T\left(\frac{n}{2}\right)$"

and following is the solution:

\begin{align} T(n) &= 2T\left(\frac{n}{2}\right) + n\\ &= 2\left(\frac{n}{2} \log \frac{n}{2} + \frac{n}{2}\right) + n\\ &= n \lg \frac{n}{2} + n + n\\ &= n\left(\lg n - \lg 2\right) + n + n\\ &= n \lg n - n + n + n\\ &= n \lg n + n\\ \end{align}

I have got so many questions and it frightens me to death that I don't grasp this concept :/

  1. Where is the inductive step here like we have in induction when working with sums e.g. prove for $n + 1$
  2. How did the author get from this: $$\dots = 2T\left(\frac{n}{2}\right) + n$$ to this $$\dots = 2\left(\frac{n}{2} \log \frac{n}{2} + \frac{n}{2}\right) + n$$
  3. I absolutely don't get the last lines of the solution : \begin{align} & = n \lg \frac{n}{2} + n + n\\ & = n\left(\lg n - \lg 2\right) + n + n\\ & = n \lg n - n + n + n\\ \end{align}

Have I forgotten basic properties of logarithms? Truth be told I have been a software developer for the past 2 years and am getting ready for my masters which start in 3 weeks..

Thanks for your patience and your time.

share|improve this question
add comment

2 Answers

up vote 0 down vote accepted

This is the recurrence relation for merge sort. By induction of successive powers of 2, your recurrence relation reduces to $\displaystyle T(n) = 2^k T \left ( \frac{n}{2^k} \right ) + c n k$.

Assuming that $n = 2^k$ and that $T(1) = 1$, then $\displaystyle T(n) = n + c n \log_2(n)$. Thus the algorithm is on the order $\mathcal{O}(n \log_{2}n)$.

share|improve this answer
    
You lost me there.. how did you and the authors get that log2 in the solution? I am especially puzzled by the authors solution to the problem. Could you mind explaning it line by line if possible? Thanks –  Peter Jan 15 '13 at 22:13
    
@Peter, Given $n = 2^k$, $\log(n) = k \log(2) \implies k = \log(n) / log(2) = \log_{2}(n)$. Thus when you take the recurrence relation in my answer, you get $n + cn \log_{2}(n)$ by substituting $2^k$ with $n$ and $k$ with $\log_2(n)$. –  lewellen Jan 15 '13 at 22:19
add comment

This recurrence has the nice property that we can compute explicit values for $T(n)$ the same way as was done here, for example. Let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ be the binary digit representation of $n.$ Assuming that $T(0)=0$, it is not difficult to see that $$ T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j} = \sum_{j=0}^{\lfloor \log_2 n \rfloor} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ For an upper bound, consider values of $n$ consisting entirely of one digits, which gives $$T(n) \le \sum_{j=0}^{\lfloor \log_2 n \rfloor} \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k = \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left( 2^{1+ \lfloor \log_2 n \rfloor} - 2^j \right) = (1+ \lfloor \log_2 n \rfloor) 2^{1+ \lfloor \log_2 n \rfloor} - 2^{1+ \lfloor \log_2 n \rfloor} + 1 = \lfloor \log_2 n \rfloor 2^{1+ \lfloor \log_2 n \rfloor} + 1.$$ For a lower bound, consider a one digit followed by zeros, which gives $$T(n) \ge \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^{\lfloor \log_2 n \rfloor} = (1+ \lfloor \log_2 n \rfloor) 2^{\lfloor \log_2 n \rfloor}.$$ Taking these two bounds together, we have shown that $$ T(n) \in \Theta\left(\lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor}\right).$$ But we have $$ \log_2 n -1 < \lfloor \log_2 n \rfloor \le \log_2 n$$ so that this is $$ T(n) \in \Theta\left(\lfloor \log_2 n \rfloor n\right) = \Theta\left(n \log_2 n\right).$$ The lower bound shows that the next term asymptotically is $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.