It's true that reading input is always O(n), in fact \omega\theta(n), but the constant ratios for both upper and lower bound are very small compared to signing, or pretty much any other operation.
Complexity analysis only says something about asymptotic behaviour (i.e. as n grows towards infinity), it doesn't say anything about small inputs or exact performance, which is the case here (100 sigs is definitely small, and we care about every scrap of performance). For small inputs, you'll want to run the code and measure it.
Complexity analysis only says something about asymptotic behaviour (i.e. as n grows towards infinity), it doesn't say anything about small inputs or exact performance, which is the case here (100 sigs is definitely small, and we care about every scrap of performance). For small inputs, you'll want to run the code and measure it.
\theta looks pretty cool here.
You are right about the difference of runtime complexity and runtime. But you aren't about making the maybe-wrong assumption that in general 100 sigs is small in terms of runtime. Maybe not true for every signing function. (that's at least how I read your post if I were noob)
My point is we are debating over crypto algos, audits and how complex these are but when it comes to plain math in computer science, nobody seems really to care about simple details which in fact can lead to security issues as well.
You are the first one who paying a bit more attention. Thank you.
