I was reading this discussion in another post where this question was raised by someone else. Before reading the discussion, I always thought SQL Server (and other DBMS) keep a global count of rows for each table somewhere in the metadata, but the discussion seems to say it isn't so. Why? Count(*) (without any filtering) being such a common operation would get huge boost if it is O(1). Even not considering COUNT(*), the total number of rows in a table is such a fundamental piece of information. Why don't they keep a note of it?
In addition, why do we need to "load" entire rows (as indicated in the post I linked) just to count them? Shouldn't indexes or PKs etc. be sufficient to count them?