Using double-and-add one multiplication with n requires O(log(n)) additions. I don't think there are more efficient methods.
Is that log2? If so, then a multiply "costs" 128 adds?
Yes, that would be the binary logarithm.
Time is proportional to the number of unique public keys. For bitcoin, all the transactions would have different public keys, so the speed up is at most 2X.
That is correct, the question is if this is significant enough to bother with it.