That really depends. Last year, I downloaded iOS 6 OTA on my (now former) iPhone 4S within 5-10 minutes of it coming out, and it had updated to iOS 6 in about the same amount of time.
Internet connection is important - I was on my university's Wi-Fi network which is about 30-40 Mbps. Much faster than my home wifi.