  We develop a randomized approximation algorithm for the classical maximum
coverage problem, which given a list of sets $A_1,A_2,\cdots, A_m$ and integer
parameter $k$, select $k$ sets $A_{i_1}, A_{i_2},\cdots, A_{i_k}$ for maximum
union $A_{i_1}\cup A_{i_2}\cup\cdots\cup A_{i_k}$. In our algorithm, each input
set $A_i$ is a black box that can provide its size $|A_i|$, generate a random
element of $A_i$, and answer the membership query $(x\in A_i?)$ in $O(1)$ time.
Our algorithm gives $(1-{1\over e})$-approximation for maximum coverage problem
in $O(p(m))$ time, which is independent of the sizes of the input sets. No
existing $O(p(m)n^{1-\epsilon})$ time $(1-{1\over e})$-approximation algorithm
for the maximum coverage has been found for any function $p(m)$ that only
depends on the number of sets, where $n=\max(|A_1|,\cdots,| A_m|)$ (the largest
size of input sets). The notion of partial sublinear time algorithm is
introduced. For a computational problem with input size controlled by two
parameters $n$ and $m$, a partial sublinear time algorithm for it runs in a
$O(p(m)n^{1-\epsilon})$ time or $O(q(n)m^{1-\epsilon})$ time. The maximum
coverage has a partial sublinear time $O(p(m))$ constant factor approximation.
On the other hand, we show that the maximum coverage problem has no partial
sublinear $O(q(n)m^{1-\epsilon})$ time constant factor approximation algorithm.
It separates the partial sublinear time computation from the conventional
sublinear time computation by disproving the existence of sublinear time
approximation algorithm for the maximum coverage problem.
