To write one bit you have to read the whole sector, modify the bit and then write the whole sector back again, so the head (not the read head, there is no such thing) will have to see the whole sector pass by twice in order to modify one bit.
Yes, but the sectors are small, and the sector will pass beneath the head again on the next disk rotation. You would have already needed a full rotation, now you just need two -- it's still O(n).
With flash the blocks are much larger, and you don't need to seek over the whole thing to read one bit. The R/W disparity is far larger.
Plus with Flash there's a rich ongoing history of using raw controllerless devices that don't present a uniform interface to the OS (like MTDs), where you implement a lot of the controller logic in the filesystem, something that was never totally true for hard disks.
Not 'totally true', but it was a lot more true in the past than it is today, logical block addressing on harddrives (especially PC drives, scsi and other non-consumer targeted drive architectures much less so) is a relatively new thing.
In the past the host did a lot more of the work that has now been offloaded to the drives, since IDE basically the whole controller moved off host onto the drive. The reasons are simple, tighter integration and lower costs as well as a uniform interface to the drive, no matter what goes on physically inside it. Nobody really cares! (well, drive manufacturers obviously do, but consumers will treat it like a black box, it either works or it doesn't, no much point in figuring out how it works).
So, flash in this sense is roughly where harddrives were in the times of the early winchester, you present a pretty rough device to the outside and the host has to know a lot about how it works to make it function.
SSDs are already changing this, the controller is built in now and the interface presented is very close to the one used by a normal harddrive, in fact most are indistinguishable. Even most usb sticks and the larger cards do a good job of hiding the gory details.
That full rotation business is not quite the whole story by the way, plenty of drives nowadays do not need to see the 'whole' track in order to do a simple read or write of a sector, they can optimize for that to the point that the sector will be just about ready to be read from or written to by the time the drive head arrives above the track.
Most drives try to avoid that situation as long as they can though, and most file systems do too by picking a block size that is a fairly large multiple of a sector.
