# getting T(n) when I get bigTheta complexity from recurrence relation

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.

## 1 Answer

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.