Evaluate the complexity of this graph coloring algorithm

[BRN]

Hello everybody,
I should evaluate the complexity of this graph coloring algorithm.
To do this, I use the adjacency matrix in which the graph nodes are the elements on the diagonal, while the elements outside the diagonal indicate if a node is adjacent to another $(A_{i,j} = 1)$ or not Adjacent $(A_{i,j} = 0)$.
The algorithm fulfill these steps:

1. - The number of coloring nodes is counted (NoDesNotCol function);
2. - For each not colored node, calculating the degree of saturation and note the row index of the node with maximum saturation degree (satDeg function);
3. - In case the degree of saturation is equal to that of another node, then consider the maximum node degree (nodeDeg function);
4. - The row index found is passed as a argument to the function that colores the node (setColor function);
5. - All this is repeated until all the nodes are colored.

int nColoredNodes = 0.;
unsigned int nodesToColor = nodesNotCol(adjMat);
while( nColoredNodes < nodesToColor)
{
    int max = -1, index = -1;
    for (int i = 0; i < adjMat.size(); ++i)
    {
        if (adjMat[i][i] == 0.)
        {
            int sDegree = satDeg(i, adjMat, matOrder);
            if (sDegree > max) { max = sDegree; index = i ; }
            else if (sDegree == max)
            {
                if (nodeDeg(i, adjMat) > nodeDeg(index, adjMat)) index = i;
            }
        }
    }
    adjMat[index][index] = setColor(index, adjMat, matOrder);
    nColoredNodes++;
}

Calculating the equation of recurrence considering that:

• - noesnotcol is $O(n)$;
• - satDeg is $O(n^2)$;
• - nodeDeg is $O(n)$;
• - setColor is $O(n^2)$;

in case $n=1$:
the cost is 1 for NodesNotCol, 1 for Satdeg, 1 for Nodedeg, 1 for SetColor. Then $$T(1) = 1 + 1 * (1 * (1 + 1) +1) = 4$$

In case $n>1$:
$$T(n) = n + n (n (n + n^2) + n^2) = n^4 + 2n^3 + n$$

So this algorithm has complexity $O(n^4)$? Is right what I did?

 

[BRN]

OK, some correction:
setDeg is $O(\sqrt n n)$
setColor is $O(\sqrt n n)$

The equation of recurrence should be

$T(n)=\left\{\begin{matrix} 4 & n=1\\ n+n(n(n+\sqrt n n)+\sqrt n n)& n > 1 \end{matrix}\right.$

On this I'm pretty sure. Now the question is:
With an equation of recurrence for the worst case

$T(n)=(1+\sqrt n)n^3+\sqrt n n^2 + n$

Is it possible to say that asymptotically is $O(n^3)$?