Privacy preserving has become an essential process for any data mining task. Therefore, data transformation to ensure privacy preservation is needed. In this paper, we address a problem of privacy preserving on an incremental-data scenario in which the data need to be transformed are not static, but appended all the time. Our work is based on a well-known data privacy model, i.e. k-Anonymity. Meanwhile the data mining task to be applied to the given dataset is associative classification. As the problem of privacy preserving for data mining has proven as an NP-hard, we propose to study the characteristics of a proven heuristic algorithm in the incremental scenarios theoretically. Subsequently, we propose a few observations which lead to the techniques to reduce the computational complexity for the problem setting in which the outputs remains the same. In addition, we propose a simple algorithm, which is at most as efficient as the polynomial-time heuristic algorithm in the worst case, for the problem. Copyright 2009 ACM.