Algoritmos y Estructuras de Datos (VJ1215)

La solución es O(|V| + |E|).

El bucle externo hace |V| iteraciones, pero no es un buen análisis multiplicar eso por |V| ni por |E| porque el bucle interno no hace cada vez |V| ni |E| iteraciones. Por cada iteración del bucle externo, el bucle interno hace exactamente tantas iteraciones como arcos salen de v. En total, combinando ambos bucles, se pasa una vez por cada arco del grafo, es decir, la instruccion contador = contador + 1 se ejecuta |E| veces.

Al coste de pasar por cada arco sumamos el coste de avanzar para pasar por cada vértice, porque eso se paga independientemente de que haya arcos o no. Cuando sabemos que el grafo tiene más arcos que vértices podemos expresar el coste total como O(|E|). En general, sin tener esa garantía, lo correcto es O(|V| + |E|). Por ejemplo, en el caso extremo de que tuviéramos |V| vértices y cero arcos, el coste de los dos bucles anidados no sería cero sino O(|V|).