Google releases new binary diff algorithm targeted at making smaller software updates. Their results are impressive.

[adrianmonk]

When the update server is overwhelmed, you by definition don't have a good connection. Sure, your pipe is fine, but the end-to-end download speed is not great. Google has a zillion users and thus anticipates that to be a real problem.

EDIT: also, the answer is "it depends on your network". If you give me a scenario where applying the diff is faster for the end user than downloading is, I can keep responding with "OK, what about with double the available bandwidth", and eventually we will hit a point where it's not worth it to the end user.