'Erase free space' does not actually free up space for you to use, strictly speaking.
The reason it exists is this:
When you store a file on your hard drive, it will appear in your folders so you can access it. It has both a physical space where it actually is on the magnetic tape of the drive (or the SSD, as the case may be), and a place in your filesystem, where you can access it.
When you delete a file, and empty your trash, you are removing it from your filesystem, and increasing the amount of space you can use for other things, but until you replace it with something else down the line, that file you deleted still physically exists on the actual drive itself, even though you can't see it.
"Erase free space" removes files that are already gone from the physical drive it occupies, permanently. The reason this feature exists, confusing as it is, is primarily to prevent others from accessing your files through data recovery if you're really paranoid. It can also improve the performance of your drive if it's getting bogged down (which shouldn't happen, because OS X is generally pretty good about file management).
But it won't create any additional usable space you don't already have.
I know it's confusing, but yeah. That's the situation.
Still, though, as has been said, it shouldn't have REDUCED the amount of available drive space by any stretch. If you're looking to free up hard drive space, I'd recommend hitting 'get info' on folders where you think large files might be lurking that you don't need anymore. There are also programs out there that can locate the largest files for you, so you can examine them to see if you'd like to get rid of them to free things up. Be careful, though, not to get rid of anything you actually need. Your optimal solution may simply be a larger hard drive.