I'm not a domain expert, but I would assume that "approaches based on sampling" could be O(1). If so, the slowness would be based on the scaling, not on the constant.
If you keep the number of samples constant (so that you can have O(1) time) then the quality of the estimate goes down with the number of items in the collection. To keep the quality constant, you need number of samples to scale with the size of the collection.
Suppose I have a set of all integers less than k and > 0, and you after N random selections want to estimate k. Presumably as k increases your accuracy drops in absolute terms. But, if you do the same thing using the reals so there is infinite number of numbers from zero to k you can still make a bounds for k.
Granted there are now infinite number of reals in your estate, but you can still pick an N such that an arbitrary % of the time k is +/- an arbitrary % of your guesses.
Not necessarily, using k samples you can estimate the mean of i.i.d. samples with a variance of 1/k the sample variance. Note that this is independent of the sample distribution, in particular it's also true if you're drawing from some fixed collection, regardless of its size.
I find it harder to say something about the median, but I imagine some similar theorems hold.
Unless you have some definition of quality for which you can show that you do need more samples with a bigger collection?
