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

• You have the correct answer in your question: O(n**2+n)=O(n**2). – ADdV Sep 27 '20 at 21:44
• 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)$ ? – Babado Sep 27 '20 at 21:48
• @ Babado Yes, exactly. You don't do a comparison for every entry in the adjacency matrix, you only do n-1 comparisons after doing the "difficult" part. On the other hand, calculating degree is O(n), but you need to do that n times, which is where the multiplication comes from. – ADdV Sep 27 '20 at 21:53
• Thank you very much! – Babado Sep 27 '20 at 21:54