constant-time: takes the same amount of time no matter what the request is.

linear-time: takes an amount of time which is some constant times the size of what was requested.

For example, storing 8GB of Pi on a server as part of a script and returning the whole thing even if the user only needs the first 4 bytes -- that's constant-time. Nobody every said it had to be fast, just constant.