Do not think that calculate 1 sig has constant runtime = O(1). It should be depend on the size of the to-be-verified payload.
Huh?
You've lost me - a sig is a sig - that is a one time function over data.
If you have a tx that outputs from X to 1000 other accounts it only requires 1 sig check at the end to verify. That will be basically 1000x faster than having a sig for each of the 1000 accounts.
Still not clear?