# Evaluate the complexity of this graph coloring algorithm

Thread moved from the technical forums to the schoolwork forums
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.
Code:
int nColoredNodes = 0.;
while( nColoredNodes < nodesToColor)
{
int max = -1, index = -1;
for (int i = 0; i < adjMat.size(); ++i)
{
{
int sDegree = satDeg(i, adjMat, matOrder);
if (sDegree > max) { max = sDegree; index = i ; }
else if (sDegree == max)
{
}
}
}
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?

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)##?