当有 $N$ 个观测样本和 $p$ 个自变量，加性模型的拟合需要应用 $mp$ 次的一维平滑器或回归方法。回修算法所需要的循环次数 $m$ 一般小于 20，通常都小于 10，其依赖于输入变量中的相关性。以三次平滑样条为例，初始化排序需要 $N\log N$ 次运算，样条拟合需要 $N$ 次运算。因此加性模型拟合一共需要 $pN\log N+mpN$ 次运算。
树模型对每个自变量的初始排序需要 $pN\log N$ 次运算，并在计算分割上通常需要 $pN\log N$ 次运算。如果分割点产生在自变量取值范围的边界附近，这个数字可能上升至 $N^2p$。
当有 $p$ 个自变量，模型中已有 $m$ 项，那么 MARS 增添一个基函数需要 $Nm^2+pmN$ 次运算。因此构建 $M$ 项的模型需要 $NM^3+pM^2N$ 次运算，若 $M$ 是 $N$ 的一个合理比例，可能对应的运算量过大。
HME 模型的每个成分在每个最大化（M）步骤的拟合计算量通常不大：回归为 $Np^2$ 次，$K$ 类别对数几率回归为 $Np^2K^2$ 次。不过 EM 算法可能收敛比较慢，所以较大的 HME 模型的拟合成本比较高。