Adding a random amount of time seems like a reasonable thing to do.
Not sure what the links are all about, or the discussion of time complexity... I mean, there isn't an "input size" to talk about big-O scaling anyway, in the case of sudo.
Timing attacks > Avoidance https://en.wikipedia.org/wiki/Timing_attack
