I did my name ammendment by mail and it took 9 days from sending it out to receiving it.
You might consider getting a whole new passport though, issued with your new name & new photo, just because a surprising number of people don't bother to look for the name ammendment, get confused, and it fuddles things up. Nothing serious, just a hassle. Like when I was at the airport recently the lady said I didn't have a seat reserved and had me panicking for oh - 10 minutes? Until she finally realized she was looking me up under my maiden name DESPITE the fact that it says - clearly - that my name had been changed. Doing it over again, I'd just have gotten a new passport. When I get back to the US I'll do just that.