Summary: We consider the problem of estimating the support size of a discrete distribution whose minimum nonzero mass is at least \(\frac{1}{k}\). Under the independent sampling model, we show that the sample complexity, that is, the minimal sample size to achieve an additive error of \(\epsilon k\) with probability at least 0.1 is within universal constant factors of \(\frac{k}{\log k}\log^{2}\frac{1}{\epsilon }\), which improves the state-of-the-art result of \(\frac{k}{\epsilon^{2}\log k}\) in [G. Valiant and P. Valiant, J. ACM 64, No. 6, Paper No. 37, 41 p. (2017; Zbl 1426.62107)]. Similar characterization of the minimax risk is also obtained. Our procedure is a linear estimator based on the Chebyshev polynomial and its approximation-theoretic properties, which can be evaluated in \(O(n+\log^{2}k)\) time and attains the sample complexity within constant factors. The superiority of the proposed estimator in terms of accuracy, computational efficiency and scalability is demonstrated in a variety of synthetic and real datasets.