Timeline for Runtime of algorithm to transpose a graph
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 8, 2020 at 9:18 | comment | added | Abhishek Ghosh | I encountered the problem of finding transpose of graph G in CLRS book. There graph is represented by adjacency list.They say that time complexity is $O(V+E)$. I know that $Θ(V+E)->O(V+E)$.But why are they specifically using $O$ while they have used $Θ$ while dealing with DFS which actually is so.While analyzing algo of transpose I found it as $Θ$. for each vertex u in G we scan the adjacency list of it and for each of the adjacent vertex v of u, u is added to the front of adjacency list of v in transpose(G).By aggregate analysis i find that it $Θ$ as each and every edge in G is explored | |
| Oct 19, 2016 at 20:36 | vote | accept | CommunityBot | ||
| Oct 19, 2016 at 18:09 | history | answered | Yuval Filmus | CC BY-SA 3.0 |