1
$\begingroup$

I wonder how could I solve the recurrence relation when I calculate complexities. Let me explain it via an example:

$T(n)=2T(n/2) +n$. Solve this recurrence relation.

I know from the Master theorem that it has a $\Theta(n \log n)$ complexity. However,I don't want to get only complexity but also equation like $T(n)=\ldots$.

Is there anyone to help me?

Thanks in advance.

$\endgroup$
0
$\begingroup$

It appears you are asking for an exact solution of the recurrence $$T(n) = 2 T(\lfloor n/2 \rfloor) + n$$ with $T(0) = 0.$ Suppose that the binary represenation of $n$ is $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$ Then the exact solution is given by $$ T(n) = \sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^k \sum_{j=k} ^{\lfloor \log_2 n \rfloor} d_j 2^{j-k} = \sum_{k=0}^{\lfloor \log_2 n \rfloor} \sum_{j=k} ^{\lfloor \log_2 n \rfloor} d_j 2^j.$$ Now to get an upper bound consider a string of ones, which gives $$T(n) \le \sum_{k=0}^{\lfloor \log_2 n \rfloor} \sum_{j=k} ^{\lfloor \log_2 n \rfloor} 2^j = \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor +1} + 1.$$ The lower bound corresponds to the case of a one followed by a string of zeros, giving $$T(n)\ge \sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^{\lfloor \log_2 n \rfloor} = (\lfloor \log_2 n \rfloor +1) 2^{\lfloor \log_2 n \rfloor}.$$ It follows that the complexity of $T(n)$ is $$T(n)\in \Theta\left(\lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor}\right)$$ with the leading coefficient fluctuating between $1$ and $2.$ This is $$\Theta\left( \log n \times n\right).$$ This link points to a series of similar calculations.

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