Abstract: This paper addresses stability issues in incremental induction of decisiontrees. Stability problems arise when an induction algorithm must revise a decision tree very often and oscillations between similar concepts decrease learning speed. We review a heuristic that solves this problem and subsequently employ asymptotic analysis to approximate the basic parameters related to the estimation of computational effort in incremental learning of decisiontrees. We then use these approximations to simplify the heuristic, we deliver insight into its amortizing behavior and argue how they can also speed-up its execution and enhance its applicability, also providing experimental evidence to support these claims.