JMich: Yes. When someone mentions complexity for passwords, I assume he means that the pool of characters is more than just the letters, so about 80 characters.
94, typically. At least on a standard English qwerty keyboard. Likely more for non-English keyboards, though there are usually limits to what websites will allow for non-English character usage for passwords, and ASCII only characters that never appear on any keyboard are almost never considered valid for passwords.
So, for the majority of computer users all over the world, with a few potential variations this means:
26 uppercase letters
26 lowercase letters
10 numbers
32 symbols (33 if you count space as a valid input for a password, though most places don't)
Which is fascinating looking at different passwords, and knowing that a typical not-too-expensive computer CPU is now capable of cycling through hundreds of millions of combinations per second (we're somewhere around 1 billion / second with a high-end 8 core i7, probably 2 billion/second with the new 16 core Xeon that just dropped. But something mid-range should easily hit 200-400 million / second), and that's only going to keep getting faster and more efficient as time goes on. That's not even looking at GPUs which are even faster.
A 4 digit numbers only password has 10,000 possible combinations (10^4).
Change to just lowercase or uppercase letters, and that number climbs to 456,976 (26^4).
Allow upper or lower and numbers and you now have 1,679,616 combinations (36^4).
Upper & lower gives you 7,311,616 (52^4).
Upper, Lower & Numbers gives you 14,776,336 (62^4)
And going full out with upper, lower, numbers, and symbols you get 78,074,896 (94^4). Granted, still well within the range of what a typical home PC can brute force in less than 1 second.
Doubling the length of the password doesn't simply double the number of combinations, however. An 8 character password with upper, lower, numbers, and symbols gives you 6,095,689,385,410,816 combinations (94^8). Now we're entering the realm where a typical home PC would take a day or two to crack, rather than seconds. But a box built specifically for brute forcing passwords with several GPUs could still do this in a very short amount of time. A password length of 8 is interesting because a disgustingly disturbing amount of bank websites still won't let you use anything longer. And most of them don't even let you use all the symbols (if they let you use any at all...)
Now you may be thinking, surely the website in question would have some limit on failed attempts and block any further attempts, at least for a while, which would significantly slow down the cracking process. And you'd be right. Even with the best case scenario of brute forcing over the internet where you can only expect to get maybe 5-10 guesses per second just due to the time it takes for data to travel back and forth, would significantly hinder the cracking process, even if there were no such restrictions on failed attempts.
That's why most password cracking isn't done on the website directly. It's most often a sql injection attack or some other method of compromising the website to get at and download the entire database. Once that database is on the computer set up to do the cracking, it's going to be bombarded with billions of guesses per second. Though it will first be put through several dictionary and rainbow table attacks that will likely reveal a shockingly high percentage of user passwords in less than a day, and then if the cracker still wants more passwords, they might turn to brute force as a last resort, but will probably set some character limits to keep it from tying up the machine for days/weeks/months/years/lifetimes, and just take what they can get within say 72 hours.
Now you may also be thinking "okay, but what about xkcd's correcthorsebatterystaple example? Wouldn't that be 26^25, or 2.3677383000796758887679516493847e+35 combinations?" Yes it would,
if it was being brute forced. But because the passphrase consists of four typical dictionary words, it's really <length of dictionary file>^4, because dictionary attacks are typically far faster than brute force. Let's use a common 100,000 word dictionary as an example, so 100,000^4 = 100,000,000,000,000,000,000. While a lot more than 94^4, it's still significantly less than 26^25 or even 94^25.
So, while length is typically better than complexity, complexity + length is the best of both worlds. And when the website only lets you have a maximum of 12 characters for a password, a passphrase is basically useless. Might as well just get in the habit of using a password manager and going for the complexity + length. I'd rather have 94^12 than use three 4 letter words or even four 3 letter words. That's 1,000,000,000,000,000 (100,000^3) or 100,000,000,000,000,000,000 (100,000^4) vs. 475,920,314,814,253,376,475,136 (94^12). And the passphrase combinations can be significantly reduced through filtering. If you know the website only accepts a maximum of 12 character passwords, and you suspect users are doing passphrases, you can simply have your cracking software only look at 2-4 letter words in that dictionary. Taking the number from 100,000 words to something far less than 100,000. Run another pass looking only at 6 letter words. And so on.
The other problem with passphrases is that as they are cracked, they get added to dictionaries of their own, so that "correcthorsebatterystaple" you can bet is already part of a dictionary and even if there are 10 million other passphrases in that dictionary, that's still only at most 10,000,000^1 guesses that need to be made to find the passphrase, and even the cheapest computer on the market could crack that in a second. 100 million passphrases would still only take a second. And this is why the best method is and will always be using randomly generated passwords consisting of upper, lower, numbers and symbols.