Time complexity of a BFS of a graph

Question

I am unable to comprehend how the time complexity of the BFS of a graph is O(v+2E), where V is the number of vertices and E being the number of edges.

/**
 * @param {number} V
 * @param {number[][]} adj
 * @returns {number[]}
*/
class Solution {
    // Function to return Breadth First Traversal of given graph.
    bfsOfGraph(V, adj) {
        const queue=new Queue();
        
        const visited=Array.from({length:V},()=>false);
        const ans=[];
        
        queue.add(0);
        visited[0]=true;

        
        while(!queue.isEmpty()){
            const el=queue.remove();
            ans.push(el);
            
            for(const v of adj[el]){
                if(!visited[v]){
                    queue.add(v);
                    visited[v]=true;
                }
            }
        }
        
        return ans;
    }
}


class Queue {
    constructor() {
        this.arr = [];
        this.start = 0;
        this.end = -1;
    }


    add(el) {
        this.arr.push(el);
        this.end++;
    }


    remove() {
        if (this.isEmpty())
            return;

        let el = this.arr[this.start];
        this.start++;

        return el;
    }

    isEmpty() {
        return this.start > this.end;
    }

    get length() {
        return this.end - this.start < 0 ? 0 : this.end - this.start + 1;
    }
}

In the above javascript implementation of the BFS of a graph, since the queue only holds the vertices that haven't been visited which makes the outer loop run for exactly V times and for each vertex, we check if it's neigbouring nodes have been visited by looking at the visited array, which in itself is an O(1) operation. So, technically for each vertex we make O(1) operations equal to the degree of that vertex. So, why isn't the TC of the algorithm equal to O(V*avg. degree of a graph).

I tried everything but still don't have a clue. I checked a similar question on stack overflow but it didn't help. Can someone explain me why it's O(V+E) instead of O(V*avg. degree of graph).

Answer 1

O(𝑉+𝐸) is (almost) the same thing as O(𝑉𝑑) where 𝑑 is the average degree. O(𝑉𝑑) is not entirely correct when the graph is not connected. Take the extreme example where the graph has no edges, then 𝑉𝑑 is 0, but obviously you still need to visit every node to find out it has no neighbors, so actually we should say O(𝑉+𝑉𝑑). With that correction they are equivalent:

As every edge connects two vertices, every edge adds one to the degree of two vertices, making the sum of the degrees equal to 2𝐸, giving us an average 𝑑 = 2𝐸/𝑉. If we substitute that in O(𝑉+𝑉𝑑) we get O(𝑉+2𝑉𝐸/𝑉) = O(𝑉+2𝐸) = O(𝑉+𝐸). Note that the factor 2 is irrelevant for big O notation and can be replaced with factor 1.

Answer 2

The average degree of the graph is 2E/V, since each edge is counted for 2 vertices and you take the average. Therefore, V*avg.degree simplifies to 2E.
so what you are saying is that BFS is O(2E)=O(E) however, in a connected graph (and BFS is for them only) There isn't really any difference between O(V+E) and O(E) since V<E