What is considered an asymptotic improvement for graph algorithms?


Lets say we are trying to solve some algorithmic problem A that is dependent on input of size n. we say algorithm B that runs in time T(n), is asymptotically better than algorithm C which runs in time G(n) if we have: G(n) = O(T(n)), but T(n) is not O(G(n)).

My question is related to the asymptotic running time of graph algorithms, which is usually dependent on |V| and |E|. Specifically I want to focus on Prim’s algorithm. If we implement the priority queue with a binary heap the run-time would be O(ElogV). With Fibonacci heap we could get a run-time of O(VlogV + E).

My question is do we say that O(VlogV + E) is asymptotically better than O(ElogV)?

Let me clarify: I know that if the graph is dense the answer is yes. But if E=O(V) both of the solutions are the same. I am more interested in what is usually defined as an asymptotic improvement in the case we have more than one variable, and even worse – the variables are not independent (V-1<=E<V^2, since we assume the graph is connected for Prim’s algorithm).

Thanks!