Performance of count(*) on large tables vs SQL Server

Doing some rather crude comparative performance tests
between PG 8.0.1 on Windows XP and SQL Server 2000, PG
whips SQL Server's ass on

insert into junk (select * from junk)

on a one column table defined as int.
If we start with a 1 row table and repeatedly execute
this command, PG can take the table from 500K rows to
1M rows in 20 seconds; SQL Server is at least twice as
slow.

BUT...

SQL Server can do

select count(*) on junk

in almost no time at all, probably because this query
can be optimised to go back and use catalogue
statistics.

PG, on the other hand, appears to do a full table scan
to answer this question, taking nearly 4 seconds to
process the query.

Doing an ANALYZE on the table and also VACUUM did not
seem to affect this.

Can PG find a table's row count more efficiently?.
This is not an unusual practice in commercial
applications which assume that count(*) with no WHERE
clause will be a cheap query  - and use it to test if
a table is empty, for instance. (because for
Oracle/Sybase/SQL Server, count(*) is cheap).

(sure, I appreciate there are other ways of doing
this, but I am curious about the way PG works here).