[igraph] Complexity of constructing an MST

[Yulia Matveyeva]

Good afternoon, dear igraph-community.

 I have read in the igraph-documentation  
(igraph Reference Manual of Csardi and Nepusz that I got from the official 
igraph web-site)
that the complexity of the algorithm for constructing a minimum spanning tree
that is used in the corresponding function
is O( |V| + |E|),
while in most traditional books on graph theory I have only found information 
about algorithms
having a complexity of O( |E| * log (|V|) ).

 Is there a mistake or could someone please give me a link to the description 
of the (new ?)
optimized algorithm ?

Thanks in advance. 

-- 
Sincerely yours,
Yulia Matveyeva,
Department of Statistical Modelling,
Faculty of Mathematics and Mechanics,
St Petersburg State University, Russia