I've a hunch (untested) that you can squeeze even more performance out of the non-partitioned case. Instead of count(*), which is normally O(n), look up the row counts in sys.partitions, which is an O(1) operation. I suspect that the actual value of count(*) at the moment you run the query doesn't matter for this application. If the table is a busy one, with lots of inserts and/or deletes happening, count(*) may not be any more accurate either.
Of course, if your table is partitioned (not the query) and the table partitioning matches that of your query, even better!