How can we write

This is analysis of prim's algo.At the end of text this particular thing is given and I am not able to understand it.Code:`O(V lg V+E lg V)=O(E lg V)`

V-No of vertices

E-No of edges

lg-log to the base 2

Printable View

- 04-01-2006vaibhavBig Oh Notation problem
How can we write

Code:`O(V lg V+E lg V)=O(E lg V)`

V-No of vertices

E-No of edges

lg-log to the base 2

- 04-01-2006Salem
Big-O only lists the most dominant term. Minor terms and constants are not shown in the final result.

- 04-01-2006vaibhav
But how can we say E>V?

- 04-01-2006Salem
> But how can we say E>V?

Isn't that in the preceding text?

I'd say than in a graph, a single vertex can be the locus of many edges (at least two for a simple vertex with an edge in, and and edge out).

Unless you have a really boring graph of two vertices and one edge, in which case the answer is pretty moot. - 04-01-2006Rashakil FolQuote:

Originally Posted by**vaibhav**