I don't see that a=? rule. By selecting "100" rows out of a million, I think that means 100 distinct dates.

In this case, I take n = 1,000,000

The first query is likely O(log(x)) where x is number of distinct values of a. I approximated that to be O(1) relative to n.

I could be wrong here, or we could have seen different questions, or we are just interpreting the question differently.