The max k-coverage problem asks us to select k subsets from a collection S of subsets of a universe U, such that the union of these k subsets covers as many elements of U as possible. We prove that for every \(\lambda \in (0,1)\) and \(k\in \mathbb {N}\) , there exists an algorithm which, given a max k-coverage instance with input size N, finds k sets that cover at least \((1-1/e+\lambda /e)\cdot opt\) elements for max k-coverage in \(O(N^{\lambda k+O(1)})\) -time, where opt is the number of elements covered by the optimal solution. On the other hand, we show that, assuming the Gap Exponential Time Hypothesis, while \(\lambda \) is a constant, the fastest \((1-1/e+\lambda )\) -approximation algorithm for max k-coverage running in \(O(N^{\alpha k + o(1)})\) time satisfies \(\alpha \ge \varOmega (\lambda ^4)\) . While non constant \(\lambda =\lambda (k)\) is a small function of k, the fastest \((1-1/e+\lambda )\) -approximation for max k-coverage running in time \(O(N^{\alpha k + o(1)})\) satisfies \(\alpha \ge \varOmega (\lambda ^\frac{1}{\lambda })\) .