This study tested five methods widely used in estimating the complete magnitudes (MC) of earthquake catalogs. Using catalogs of observed earthquake properties, we test the performance of these five algorithms under several challenging conditions, such as small volume of events and spatial-temporal heterogeneity, in order to see whether the algorithms are stable and in agreement with known data. We find that the maximum curvature method (MAXC) has perfect stability, but will significantly underestimate MC unless heterogeneity is absent. MC estimated by the b-value stability method (MBS) requires many events to reach a stable result. Results from the goodness of fit method (GFT) were unstable when heterogeneity lowered the fitness level. The entire magnitude range method (EMR) is relatively stable in most conditions, and can reflect the change in MC when heterogeneity exists, but when the incomplete part of the earthquake catalog is dismissed, this method fails. The median-based analysis of the segment slope method (MBASS) can tolerate small sample size, but is incapable of reflecting the missing degree of small events in aftershock sequences. In conditions where MC changes rapidly, such as in aftershock sequences, observing the time sequence directly can give a precise estimation of the complete sub-catalog, but only when the number of events available for study is large enough can the MAXC, GFT, and MBS methods give a similarly reliable estimation.