Given a set of gene trees, the DUPLICATION-LOSS problem is to infer a comparable species tree minimizing the number of gene duplications and losses (the mutation cost). This problem has been shown to be NP-hard. A standard heuristic performs the stepwise local searches on the tree space until a local minimum is reached. In this paper, we study the heuristic for the DUPLICATION-LOSS problem based on NNI local searches and propose a linear-time algorithm for the NNI LOCAL SEARCH problem under the mutation cost. Bansal et al. presented a near-linear time algorithm for the NNI LOCAL SEARCH problem under the duplication cost, and we also improve the result of Bansal et al. with a linear-time algorithm.