Solving recurrence relation $T(n)=\sqrt{n} \cdot T(\sqrt{n}) + n$ using method of guessing and confirm?
The book answer skips over some things. Here's a more detailed explanation.

You want to show $T(n)=O(n\log n)$, in other words there exists a $c&gt;0$ such that $T(n)\le c\cdot n\log n$. [Actually, you need also to show that this inequality holds for all $n$ greater than some constant $N$, but we'll put this off temporarily.]

We'll use strong induction here; our induction hypothesis is that 


  $T(k)\le c\cdot k\log k$, for all $k&lt;n$.


Now we'll expand the book's answer.
$$\begin{align}
T(n) &amp;= \sqrt{n}\;T(\sqrt{n}) + n &amp;\text{by definition} \\
     &amp;\le\sqrt{n}\;[c\cdot\sqrt{n}\log{\sqrt{n}}]+n &amp;\text{by induction hypothesis, since $\sqrt{n}&lt;n$}\\
     &amp;= cn(\log\sqrt{n})+n
\end{align}$$
which answers your question about the step from $(1)\rightarrow(2)$. To get $(4) \rightarrow(5)$ the text wants to end up with $T(n)\le c\cdot n\log n$, so to conclude this they need
$$
n\cdot c\cdot\frac{1}{2}\log n+n\le c\cdot n\log n
$$
Dividing both sides of the desired equality by $n$ yields the needed condition:
$$
\frac{c}{2}\log n+1\le c\log n
$$
and this will be true when $1\le \frac{c}{2}\log n$. [The book actually doesn't need an unspecified $c$: in fact, $c=2$ will work perfectly here, since as long as $n\ge 2$ we'll have $1\le\log n$, satisfying our needed condition.]

In sum, we've shown by induction that the recurrence $T(n)= \sqrt{n}\log\sqrt{n}+n$ is satisfied by any function $T(n)=c\cdot n\log n$, as long as we pick a suitable $c$, which is exactly what was required.  



It's worth pointing out that $O(n\log n)$ is an upper bound, but it's not the tightest upper bound possible. As gnasher729 pointed out, a better bound is $O(n\log\log n)$. It's a good exercise to do the same argument (with $c=1$) to show that $T(n)=n\log\log n$ is a solution to $T(n)=\sqrt{n}\;T(\sqrt{n})+n$.