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
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
Big-O only lists the most dominant term. Minor terms and constants are not shown in the final result.
But how can we say E>V?
> 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.
Why even mention the base? It doesn't matter.Quote:
Originally Posted by vaibhav