Is there a way to study precisely the complexity with respect to the size of vertex set for some graph problem?
I will try to lift some of the confusion you have.
Let $G$ be some graph, with $n$ vertices and $m$ edges. Then what is $|G|$? Lets say we encoded it as adjacency matrix, so it takes up $n^2$ space. Therefore, $f(|G|)=f(n^2)$ and $g(|G|)=g(n^2)$. There won't be a &quot;gap&quot; here.
What about if we encode it with $m\log(n)$ space? then we would have $|G|=m\log(n)$ and thus $f(|G|)=f(m\log(n))$ and $g(|G|)=g(m\log(n))$.
So what went wrong with your calculations? The difference here is that you used max once and min once to represent the same quantity. You probably did this to &quot;give a bound&quot; only, but notice the following interesting thing: why would we want max? we can always encode the graph in the smallest way possible, so essentially $|G|=\min \{n^2,m\log(n)\}$. Substitute this and get $g(|G|)=g(\min \{n^2,m\log(n)\})$. In the same way, $f(|G|)=f(\min \{n^2,m\log(n)\})$.
Notice I didn't give the bounds in terms of $\Omega$ and $O$, but we could. In any case, the transition $g(\min \{n^2,m\log(n)\})=\Omega(g(n\log(n)))$ is not strict, since there are many times that $\min \{n^2,m\log(n)\}&gt; n\log(n)$. The same goes with the transition $f(\min \{n^2,m\log(n)\})=O(f(n^2)))$ (making this a min automatically made the bound better).
I hope this helped you understand a bit more how the bounds behave with respect to the size of the graph and its different encodings.