in the textbook of CLRS, p.1062 he says the following:

if we use "reasonable" encoding of a graph as its adjacency matrix, the number m of vertices in the graph is $\Omega (\sqrt n)$, where n = |$\langle G\rangle|$ is the length of the encoding of G.

I want to know why $\Omega (\sqrt n)$? I mean it is adjacency matrix which takes $m^2$ but I don't know how he calculates it, so I would like someone to explain to me how we get this time complexity?

Thank you!

  • $\begingroup$ Is it time complexity? I suspect it is the number of vertices that can be encoded using adjacency matrix of size $n$. BTW, quote says exactly this. $\endgroup$ – rus9384 Sep 26 '17 at 16:52
  • $\begingroup$ It's not a time complexity: it's just a bound on a function. $\endgroup$ – David Richerby Sep 26 '17 at 16:59

An $m\times m$ adjacency matrix requires $m^2$ bits, and $m=\sqrt{n}$ is just the solution to $m^2 = |\langle G\rangle| = n$.

The point of the $\Omega$ is that a reasonable encoding doesn't have fewer than $\sqrt{n}$ vertices in a description of length $n$. For example "Write out the $k\times k$ adjacency matrix followed by $2^k$ zeroes" isn't "reasonable" and a string of length $n$ would encode a graph with only about $\log n$ vertices.


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.