# Time complexity for computing the highest degree vertex

Consider an undirected and unweighted graph with $$n=|V|$$ nodes and $$m=|E|$$ edges stored in adjacency matrix format. What is the time complexity of finding the highest-degree vertex, assuming the vertices are given to you in no particular order?

The answer is $$\mathcal{O}(n^2)$$ but I don't know how to get there.

I divided this question in two parts:

1. time complexity of computing a degree of a given vertex

2. finding the vertex with highest degree

This is what I think:

It takes $$\mathcal{O}(n)$$ to compute the degree of a given vertex $$i$$ (sum $$n$$ values in row $$i$$). Doing this for all vertices, we get $$\mathcal{O}(n^2)$$.

But then we need $$n-1$$ comparisons in order to conclude which vertex has highest degree, which would take $$\mathcal{O}(n)$$.

So putting it all together we would get $$\mathcal{O(n\times n\times n)}=\mathcal{O}(n^3)$$ (or is it $$\mathcal{O}(n^2+n)=\mathcal{O}(n^2)$$?)

Someting is wrong with my reasoning but I don't know what. Could you tell me my mistake?

• So we compute the degree for each vertex ($\mathcal{O}(n^2)$) and then do n comparisons ($\mathcal{O}(n)$) which amounts to $\mathcal{O}(n^2)+\mathcal{O}(n)=\mathcal{O}(n^2)$ ? Sep 27 '20 at 21:48