Ace textbook

Question

What is the time complexity of best algorithm that decides whether a given directed

graph represented as adjacency Matrix contains a sink or not ?

(a)O(V^2)

(b)O(VlogV)

(c)O(V^2logV)

(d)O(V)

Comments

O(V^2)

Answer 1

To decide whether a $sink$ exists from an adjacency matrix, we need to traverse the whole matrix in the worst case. So the best algorithm requires $O(V^2)$ comparisons.

On the other hand, to find if a $universal\space sink$ exists from an adjacency matrix, the best algorithm requires $O(2V) = O(V)$ operations only, as we can skip each row and column on one comparison.

So, the answer is, $a$) $O(V^2).$