title: What is the Time complexity for finding universal sink given the adjecency list representation
body: <p>There are many variants of this question asking the solution in <code>O(|V|)</code> time. </p>
  
  <p>But what is the worst case bound if I wanna compute if there is a universal sink in the graph and I have graph represented in adjacency lists. This is important because all other algorithms seem to be better for adjacency lists, so if finding universal sink is not too frequent operation that I need, I will definitely go ahead for lists rather than matrix.</p>
  
  <p>In my opinion, the time complexity would be the size of the graph, that is <code>O(|V| + |E|)</code>. the algorithm for finding universal sink of a graph is as follows. Assuming in-neighbor list, Start from the index 1 of a graph. Check the length of adjacency list at index <code>1</code>, if it is <code>|V| - 1</code>, then traverse the list to check if there is a self loop. If list does not have a self loop <code>and</code> all other vertices are part of a list, store the list index. Then, we must go through other lists to check if this vertex is part of their list. If it is, then the stored vertex cannot be a universal sink. Continue the search from the next index. Even if list is out-neighbor list, we will have to search the vertices which have list with <code>length = 0</code>, then search all other lists to check if this vertex exists in their respective lists. </p>
  
  <p>As it can be concluded from above explanation, no matter what form of adjacency list is considered, in worst case, finding the universal sink must traverse through all the vertices and edges once, hence the complexity is the size of the graph, i.e. O(|V|+|E|)</p>
  
  <p>But my friend who has recently joined as a assistant professor at a university, mentioned it has to be <code>O(|V|*|V|)</code>. I am reviewing his notes before he starts teaching the course in the spring, but before correcting it I wanna be one hundred percent sure. </p>