Solving recurrence relation $T(n)=\sqrt{n} \cdot T(\sqrt{n}) + n$ using method of guessing and confirm?

The book I am following explains the solution as,


As we can see,the size of sub problems at the first level of recursion
is $n$.So, let us guess that $T(n)=O(n\log n)$ and try to prove that our guess is correct.

Doubt- Does initial problem size(i.e n) give a hint to reach $O(n\log n)$ ? How it does?

furthermore ,the book says


Let's start by trying to prove an upper bound $T(n)\le c\cdot n\log n$


\begin{align*}
T(n)=\sqrt{n} \cdot T(\sqrt{n}) + n \tag{1}
\\
\le \sqrt{n}\cdot c\sqrt{n}\log(\sqrt{n}) + n \tag{2}
\\
=n\cdot c\log (\sqrt{n})+ n \tag{3}
\\
=n\cdot c\cdot\frac{1}{2}\log n+ n \tag{4}
\\ \le c\cdot n\log n \tag{5}
\end{align*}
Last inequality assumes only that $$1\le c\cdot\frac{1}{2}\cdot \log n$$
This is correct if n is sufficiently large and for any constant c,no matter how small.So we are correct for upper bound.

I am not getting what's happening from $(1)$ to $(2)$ and that from $(4)$ to $(5)$. Also What does the last line prove ?

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

Now we'll expand the book's answer.
$$\begin{align}
T(n) &= \sqrt{n}\;T(\sqrt{n}) + n &\text{by definition} \\
&\le\sqrt{n}\;[c\cdot\sqrt{n}\log{\sqrt{n}}]+n &\text{by induction hypothesis, since $\sqrt{n}<n$}\\
&= 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$.

StackExchange Computer Science Q#60513, answer score: 5