The point of Fizzbuzz is that some people simply cannot write any code at all.
It's not necessarily looking for the best possible answer. In fact, I completely expect (as both interviewee and interviewer) that the candidate will write a first pass on paper, we will look at it, figure out it's big-O, and then go on to improve it to be better.
That is a fair point, too. I have done some interviews where I questioned how the person got far enough into the process that I was involved. However I have also seen the flip side of the coin where a developer/manager interviewed and subsequently rejected someone who was likely a great candidate over an on the spot brain quiz, and one that the candidate would likely NEVER see while performing his/her job duties.
It's not necessarily looking for the best possible answer. In fact, I completely expect (as both interviewee and interviewer) that the candidate will write a first pass on paper, we will look at it, figure out it's big-O, and then go on to improve it to be better.