A fast format (sometimes called quick format) only recreates the necessary table structures for the filesystem. The files aren't actually deleted, but when the table structures are reset to it's initial state they will be overwritten in time. This is because the system marked those positions as 'writable'.
A normal format recreates the table structures and clears out every block on the hard drive.
You can manually set the blocks to zero if you want using a tool like 'dd' on Linux.
A full format does not just clean the partition table data, it also checks every sector on the disk surface for corrupted ones. This is primarily why it takes so much longer to perform then a quick format. A quick format just rewrites the partition tables.
From a performance standpoint, there is no difference. When the HDD writes a file to the disk, it just finds the next available "free sector", and overwrites whatever is there (regardless of whether or not it is a 0 or a 1). Think of it like this: a quick format just "deletes" all of the files, whereas a full format performs a sector check of the drive surface, and depending on the formatting utility, may fill the drive with zeroes (the default format utilities included with Windows do not zero-fill the drive. Most disk manufacturers provide diagnostic utilities which include the ability to do this.
If the drive is brand new, you should be fine with a quick format. If the drive has corrupted sectors (or even if you think that it does), it would be worth your time to do the full format. If you want to play it safe, ensure that you do at least one full format to the drive. That should reveal all bad sectors, and from then on, you can just do quick formats.
Best Answer
Before answering this, you should know how a file system is built. A file system is a kind of library in which we have books that represent files. These books can be found using the Library's catalogue, telling you in which shelf the books are stacked.
Over time, the catalogue will still contain books that are no longer present in the library or books will be in the library that are not recorded in the catalogue. There will be decay in the system and errors might occur. Also the library might decay and fall into ruin.
When we delete all files from a media, we clear out the entire catalogue but leave all the books in the shelves. When we want to add a file (book), we make room for the new book by removing some of the other old books from the shelf and putting the new book there.
However, if we format the media, we demolish the entire library and rebuild it. The books may then still be recovered from all the rubble of the old library, but once the new library is getting filled up, that books will decay.
There's no real reason to format several times. Media, as well as hard drives and especially USB thumb drives have a number of write cycles in which according to the manufacturer, proper operation is guaranteed. Formatting media will contribute to the number of write cycles being done. Yet, you won't actually damage the drive.
From Wikipedia: