# 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(E\log V)$$. With Fibonacci heap we could get a run-time of $$O(V\log V + E)$$.

My question is do we say that $$O(V\log V + E)$$ is asymptotically better than $$O(E\log V)$$?

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\le E, since we assume the graph is connected for Prim's algorithm).

Thanks!

Suppose that $$f(V,E),g(V,E)$$ are two running times of graph algorithms solving the same problem.
We say that $$f$$ is an asymptotic improvement in some regime on $$g$$ if there exists a sequence $$V_n,E_n$$ with $$V_n \to \infty$$ such that $$\lim_{n\to\infty} \frac{f(V_n,E_n)}{g(V_n,E_n)} = 0.$$
Note also that the problem already manifests itself for one-variable functions. Consider $$f(n) = n^2, \qquad g(n) = \begin{cases} 2^n &\text{if } n = 2^m, \\ n & \text{otherwise}. \end{cases}$$ Is $$f$$ an asymptotic improvement over $$g$$? It is for inputs of a certain length, and is indeed so under our permissive definition above.