CODEWITHSUNDEEP
time-complexityadjacency-matrixtopological-sort
Noa Minsker
Noa Minsker

Reputation: 39

Topological sort for adjacency Matrix

Given a graph represented as an adjacency matrix, how can I do a topological sort in linear time? Even if I do a preprocessor to create an array of the in-degree value it will be with the time complexity of O(|V|^2). I know that for a topological sort from a matrix it is possible to create an algorithm of linear time, so what am I missing?

Upvotes: 1

Views: 3059

Answers (1)

Orr Goldman
Orr Goldman

Reputation: 35

As dyukha mentioned in the comments, "linear time" is a term that is dependent on the input size. Thus for example the trial division method for testing if a number is prime runs for at most n^(0.5) iterations, but the input size is log(n), so time complexity would be 2^(n/2).

In this case, adjacency matrix takes O(k)=O(|V|^2) space, you can apply Kahn's algorithm and get linear time, considering finding all vertices with no incoming edges by iterating the matrix takes O(k) time and going over all the edges of a given vertex takes O(k^0.5).

If your intention was whether there exists an algorithm of finding a topological sort in O(|V|), I think any algorithm would at least have to go over all edges, so that might be a lower bound.

Upvotes: 1

Related Questions