int maximumDegree() { int maxDeg = 0; for(int i = 0; i < numVertices; i++) { Vector nbrs = getNeighbors(map[i]); if(nbrs.size() > maxDeg) maxDeg = nbrs.size(); } return maxDeg; }
int maximumDegree() { int maxDeg = 0; for(int i = 0; i < numVertices; i++) { int temp = ((DoublyLinkedList)adjList[i]).size(); if(temp > maxDeg) maxDeg = temp; } return maxDeg; }
Notes:
The first function runs in O(n^2) time because the for-loop has n iterations and
in each iteration, the function getNeighbors() is called and this takes
O(n) time to execute.
It is possible to implement this function without calling getNeighbors() and
just scanning row i of the adjacency matrix and count the number of 1's (or true's).
The running time of this alternate implementation would be the same.
The second function takes O(n) time because getting the size of the doubly linked list
that contains the neighbors of the vertex i, takes O(1) time, for each i.
Since the for-loop executes n times, the total running time is O(n).