# Why encoding of graph in adjacency matrix is $\Omega (\sqrt n)$?

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!

• 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. – rus9384 Sep 26 '17 at 16:52
• It's not a time complexity: it's just a bound on a function. – 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.