I'm trying to follow CLRS ("Introduction to Algorithms") and I just hit a question in a practice assignment I found online that I just can't make any sense of.

Consider this problem:

> 
> Show that the solution of the following recurrence is $O(n\lg n)$:
>  $T(1)=2, T(2)=6, T(n) = 2T(⌊n/2⌋) + n$, where $⌊n/2⌋$. Also, conclude
>  that the solution is $\Theta(n\lg n)$ by proving that the solution is
>  $O(n \lg n)$. Solve for constants and boundary conditions. Do not
>  ignore the floor function.
> 
> 
> 

It's trivial to use to substitution method to show that $T(n) = 2T(⌊n/2⌋) + n$ is $O(n\lg n)$, but I'm not sure what I'm supposed to do with the provided boundary conditions.

One thing we can state is that since $T(n) \le cn\lg n$ and $T(2) \le c2\lg 2$, then $ c \ge 6$ (note that $T(1) \le c1\lg 1$ does not hold). I'm not sure what to do next.

I don't understand the logic .