Is there a way to study precisely the complexity with respect to the size of vertex set for some graph problem?

Suppose there is graph problem $L$ such that the instance $x$ of $L$ is a simple graph with $n$ vertices and $m$ edges.

In the Turing machine model, we can encode a graph using $O(n^2)$ cells or $O((m+1)\log n)$ cells.
(i.e., $|x| = O(n^2)$ or $|x| = O(m \log n)$).

Now I want to study the lower bound and the upper bound on the time/space complexity with respect to the number of vertices $n$. Suppose we have found the upper bound is $O(f(|x|))$ and lower bound $\Omega(g(|x|))$. Since $m = O(n^2)$ and $m = \Omega(n)$, we can only conclude that
$$O(f(|x|)) = O(\max\{f(n^2), f(m\log n) \}) = O(f(n^2\log n))$$
and
$$\Omega(g(|x|)) = \Omega(\min \{g(n^2), g(m\log n)\}) = \Omega(g(n\log n))$$
The gap become larger. It is not tight even $f = g$.

Is there way to solve my confusion?

Now I define the graph problem as a pair $(L', O)$ where for every instance $x'$ of $L'$, it is only encoded by the number of vertices, $O$ is an oracle whose valid input is a pair of vertices $(u,v)$, it returns 1 if $uv$ is an edge in the graph and it returns 0 otherwise. Can I solve my confusion by using this model? (However it seems that $|x'| = O(\log n)$ which is very small.)

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 "gap" 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 "give a bound" 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)\}> 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.

StackExchange Computer Science Q#140698, answer score: 2