Изменения

* <tex dpi="145">L_A = O(2^k) = O(\frac{2^{\log_2 n}{) = O(n})</tex>* <tex dpi="145">L_B \leq (s - 1) \cdot (t(1) + t(2) + ... + t(p)) < sp \cdot 2^s = 2^{k + s} = \frac{2^n}{n}</tex>* <tex dpi="145">L_C = O(p \cdot 2^{n - k}) = O\left(\frac{p}{n} \cdot 2^n\right) = O\left(\frac{2^n}{s}\right) = O\left(\frac{2^n}{n - 2\log_2 n}\right)</tex>* <tex dpi="145">L_D = O(2^{n - k}) = O\left(\frac{2^n}{n}\right)</tex>

Итого, имеем схему c числом элементов <tex>L_A + L_B + L_C + L_D = O(n) + O\left(\frac{2^n}{n}\right) + O\left(\frac{2^n}{n - 2\log_2 n}\right) + O\left(\frac{2^n}{n}\right) = O\left(\frac{2^n}{n}\right)</tex>, откуда следует, что <tex>size_B (f) = O\left(\frac{2^n}{n}\right)</tex>, '''''ч.т.д.'''''