It seems "constant-time" isn't used to mean "the time taken is O(1) regardless of the size of the input n", but rather, "for a given input size, the algorithm is carefully written to do the same amount of work no matter what the specific bits of the input are, to defeat timing attacks". This took me a bit of time to figure out.

To illustrate the kind of thing it's talking about, consider the naive algorithm for computing a^n via exponentiation by squaring:

  total = 1
  while n > 0:
    if n is odd:
      total = total*a
      n = n-1
    a = a*a
    n = n/2
  return total

If n has k bits, and j of them are 1s, then there will be k-1 squarings of a, and j multiplications of total by a. An attacker who can measure the total time may be able to at least figure out the number of 1 bits in n. If they can get fine-grained observations of power draw or something, then they might even be able to tell which bits are 1.

Consider this alternative:

  total = 1
  while n > 0:
    maybe_total = total * a
    if n is odd:
      total = maybe_total
    a = a * a
    n = n >> 1
  return total

This will do the same number of multiplications, if you can convince the compiler to not do any optimizations. Note that it still has a branch, though, which might conceivably be detectable. To plug that hole, something like this might work:

  # if n is odd:
  #   total = maybe_total
  # becomes this:
    low_bit = n & 1 # i.e. 0 or 1 if n is odd or even
    mask = low_bit - 1 # i.e. "all 1s" or 0 respectively
    total = (total & mask) | (maybe_total & ~mask)