You wouldn't need 4096 if the choice of the salt was non-random; some versions of Unix used the first 2 characters of the username. What's the space requirement for a single rainbow table?