Counting Work Not Updates

A training set has $n = 1{,}000{,}000$ examples. To reach the same training loss:

method	updates needed	examples per update
full-batch gradient descent	500	1,000,000
minibatch SGD, batch size 100	20,000	100

Count per-example gradient evaluations, the dominant cost in both. Which comparison is right?

Both process $10^{6}$ examples per pass, so total cost is the same

$5 \times 10^{8}$ versus $2 \times 10^{6}$ , so SGD does 250x less work

$5 \times 10^{8}$ versus $2 \times 10^{7}$ , so SGD does 25x less work

500 versus 20,000 updates, so full-batch is 40x cheaper