# Linear time algorithms on regular graphs

For each constant $k$, the number of $k$-regular graphs is of the order of $n^{\Omega(n)}$. Therefore, we need $O(n\log n)$ bits to represent k-regular graphs unambiguously.

Let $k=3$ for simplicity. There are several algorithms that run in time $O(n)$ on $3$-regular graphs with at most $n$ vertices. For instance, determining if a graph is bipartite.

How is that possible, if only to read the input we need to read $O(n\log n)$ bits?

• 1) "O(n log n) bits to represent k-regular graphs" -- unless you tell us how k and n relate, that doesn't make much sense. Or should your first sentence contain "with n nodes"? (Also, you want another $\Omega$ there.) 2) O(n) time in what model? – Raphael Sep 7 '16 at 22:32
• This is a common $\log N$ factor for all algorithms that work on N distinct entities that require enumeration. Also the mean physical distance to data in space is $O(\sqrt{N})$, so we can also multiply complexity for all algorithms by this factor, because every data access will take $O(\sqrt{N})$ time. Yet these factors do not matter unless you're programming a cache-aware or "big data" version of an algorithm. – polkovnikov.ph Sep 8 '16 at 9:42

We usually analyze algorithms on the RAM machine model, in which each operation on a machine word has unit cost. A machine word consists of $O(\log n)$ bits, where $n$ is the bit-size of the input, or some other equivalent property. Thus representing a $k$-regular graph takes only $O(n)$ machine words, so there is no contradiction.