Verifying Hamiltonian Cycle solution in O(n^2), n is the length of the encoding of G

Question

In the textbook of CLRS, 'ch. 34.2 Polynomial-time verification' it says the following:

Suppose that a friend tells you that a given graph G is hamiltonian, and then offers to prove it by giving you the vertices in order along the hamiltonian cycle. It would certainly be easy enough to verify the proof: simply verify that the provided cycle is hamiltonian by checking whether it is a permutation of the vertices of $V$ and whether each of the consecutive edges along the cycle actually exists in the graph. You could certainly implement this verification algorithm to run in $O(n^2)$ time, where $n$ is the length of the encoding of $G$.

To me, for each consecutive pair $(u,v)$ of the given cycle, we could verify if it's an edge in $G$. Further we could use some color coding for each vertex to ensure we don't revisit a vertex. By doing so, we could verify if the given cycle is Hamiltonian in $O(E)=O(m^2)$ time where $m$ is the number of vertices in $G$. Further we can see the minimum encoding $n$ of $G$ is $m^2=n$. Thus $O(E)=O(m^2)=O(n)$. Can anyone help me understand, why it is mentioned as $O(n^2)$ instead!

Answer 1

The statement in CRLS is not wrong in any case; an algorithm that runs in $O(n)$ time also runs in $O(n^2)$ time. Of course, it would be more precise to state the running time as $O(n)$ if this were true, so why doesn't CLRS do this?

First off, this depends on the encoding chosen for $G$. If an adjacency matrix is used, a graph with $V$ vertices always has an encoding of size $V^2$. However, if an adjacency list encoding is used, we would only need an encoding of size $O(E \log V + V)$.

Your algorithm does indeed run in $O(n)$ time for a dense graph (with $\sim V^2$ edges); does it also run in $O(n)$ time if the graph is sparse ($O(V)$ edges)? In that case, the encoding might be shorter (if an adjacency matrix is used). Is your algorithm still $O(n)$ in that case? If it enumerates over all potential edges or creates and adjacency matrix, it would not be.

CLRS wants to avoid peculiarities with having to implement the algorithm in a particular way or having to specify a specific encoding, which is why they state "you could certainly implement this algorithm to run in $O(n^2)$ time". The "certainly" means "in any case, you can get $O(n^2)$, but it might be possible to do better". In any case, all they care about is that it is polynomial, which both $O(n)$ and $O(n^2)$ are.