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. 
 A: 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.
