Content deleted Content added
Tags: Reverted Visual edit |
m Reverted edit by 115.247.219.102 (talk) to last version by Jochen Burghardt |
||
Line 60:
== Analysis ==
=== Time and space complexity
The [[time complexity]] can be expressed as <math>O(|V|+|E|)</math>, as every vertex and every edge will be explored in the worst case. <math>|V|</math> is the number of vertices and <math>|E|</math> is the number of edges in the graph.
Note that <math>O(|E|)</math> may vary between <math>O(1)</math> and <math> O(|V|^2)</math>, depending on how sparse the input graph is.<ref name=clrs>{{Introduction to Algorithms|edition=2|chapter=22.2 Breadth-first search|pages=531–539}}</ref>
| |||