Personally I'd use...
<?
$db = mysql_connect("localhost", "username", "password");
mysql_select_db("dbname",$db);
$query = mysql_query ("select * from table_to_test",$db);
if ($query) {
echo "Table exists!";
}
else {
echo("<P>Error: " .
mysql_error() . "</P>");
}
?>
May look longer, but it should execute faster as you are just grabbing all information, not doing anything (like counting the rows) with it.
Of course, if you know the name of a field in the db your testing, like id, putting in id instead of * will speed it up more.