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?

  • 1
    $\begingroup$ You have the correct answer in your question: O(n**2+n)=O(n**2). $\endgroup$ – ADdV Sep 27 '20 at 21:44
  • $\begingroup$ 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)$ ? $\endgroup$ – Babado Sep 27 '20 at 21:48
  • 1
    $\begingroup$ @ 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. $\endgroup$ – ADdV Sep 27 '20 at 21:53
  • $\begingroup$ Thank you very much! $\endgroup$ – Babado Sep 27 '20 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.