CODEWITHSUNDEEP
algorithmgraphruntime
Sayuri
Sayuri

Reputation: 63

Develop an algorithm running time O(nlogn)

Can you give me an hint how to develop an algorithm as this task? Everytime if I am reading something like this I don't know how to develop with using the run time. Thanks!

Give an algorithm that determines whether or not a given undirected graph G = (V;E) contains a cycle. Your algorithm should run in O(|V|) time, independent of |E|.

Upvotes: 0

Views: 211

Answers (1)

Jakub Swistak
Jakub Swistak

Reputation: 314

Currently, there aren't algorithms for that problem working with only |V|, obviously, you can conclude some cases for example if |E| >= |V| and every edge is different(different pair) there will be a cycle, but it's not necessary. You can consider also more cases for example when |V| <= 2 or |E| <= 2.

Upvotes: 1

Related Questions