Another obvious example: What's the mean of an unsorted list of integers? If you do a random sample of sqrt(n) values and mean over that, you guess is with high

Another obvious example: What's the mean of an unsorted list of integers? If you do a random sample of sqrt(n) values and mean over that, you guess is with high probability pretty good. Or a log(n) sample. (That's how election polling works too which uses even a O(1) sample though not random.) Edit: Ah, GP asked for deterministic exact.