Content deleted Content added
→Pseudocode: suggest to inline images, to save vertical space |
Tags: Reverted Visual edit |
||
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>
| |||