[grafos] O(n+m) x O(max{n,m})

[Jose Coelho de Pina <coelho@ime.usp.br>]

Ois,

Quando escrevemos que as buscas em largura e profundidade
gastam tempo O(n+m) [linear], no fundo estamos escrevendo que
o consumo de tempo é O(max{n,m}), certo? Existem pessoas que
preferem escrever O(max{n,m}) a escrever O(n+m), isto é uma
questão de gosto.  

Notem que, apesar dos grafos que imaginamos terem mais
arcos que vértices isto, em geral, não é verdade.  Assim,
não podemos escrever que as buscas em largura e profundidade
gastam tempo O(m), já que para grafos (digamos) sem arcos o
consumo de tempo é O(n).

coelho