2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Raphael Sep 7 '16 at 22:32
  • $\begingroup$ 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. $\endgroup$ – polkovnikov.ph Sep 8 '16 at 9:42
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.