In simpler terms, it always runs in exactly k time.
It is a difficult problem. It's also a critically important one when you're doing things like cryptography. Maybe we look at different kinds of algorithms, because while I see a lot of worrying about O(n) vs. O(logn) vs. O(nlogn) vs. O(n^2), most of the time when I see people worry about whether something is constant or not, they mean truly constant, not asymptotically. They are worrying about side channels.
In relation to side-channel attacks, wouldn't it be sufficient to just pad the difference between upper and lower bounds using no-ops?
I'll keep that in mind so I don't give wrong impressions in the future.
>In relation to side-channel attacks, wouldn't it be sufficient to just pad the difference between upper and lower bounds using no-ops?
It can be extremely difficult to design algorithms so that they spend the same amount of time no matter what the input number is. You can't just use no-op instructions because you don't know how many cycles things will take, no-ops aren't perfect at soaking up extra time, and they don't help at all against something like an attacker on the same EC2 host. Even worse is if you have the OS interrupt mid-computation and wreck the cycle-accurate counters that would tell you how many no-ops to use. You want to design it so that the same instruction sequence happens every time, without branching based on input, without having varied memory accesses based on input. And avoiding other variable length pitfalls like division.
It's also difficult to talk about constant time outside of an asymptotic context. There are a number of subtle sources for timing variances (e.g. branches, branch mispredicts, cache misses, pipeline stalls, context switches, etc..).