Why is the complexity of the BFS O(V + E)? Consider the algorithm (from another question):

set start vertex to visited
load it into queue
    while queue not empty
        for each edge incident to vertex
             if its not visited
                 load into queue
                 mark vertex


The complexity of the algorithm is defined as the upper bound of times the inner loop can run, right? Well, considering a complete graph. For each one of its N vertexes, we run the check if its not visited N-1 times. So, that's N * (N-1) tests, which is quadratic. What is wrong with this view?
Overall, BFS accesses (and processes) each edge constant times (twice actually; we assume an undirected graph), costing $O(E)$ total time in edge processing. Similarly, all the vertices are totally accessed (including queue operations and checking operations) $O(E) \cdot O(1)$ times. The overhead for initialization is $O(V)$. Thus the total running time of BFS is $O(V + E)$. 

This can be viewed as a simple instance of aggregate analysis.