diff options
author | Jim Meyering <meyering@redhat.com> | 2009-09-13 12:11:57 +0200 |
---|---|---|
committer | Jim Meyering <meyering@redhat.com> | 2009-09-13 12:11:57 +0200 |
commit | f6f78f093b57f2abf82c2ba3d7bf65e533af6ae7 (patch) | |
tree | 7df20f015b096645b8c116de52f5e6c79cc036d7 | |
parent | 21b617b78b5f53c1b6e1447f1709b1c2aa9f466f (diff) | |
download | coreutils-f6f78f093b57f2abf82c2ba3d7bf65e533af6ae7.tar.xz |
doc: NEWS: say quadratic and linear, rather than O(N^2) and O(N)
* NEWS: Use a slightly less technical description.
Suggested by Andreas Schwab.
-rw-r--r-- | NEWS | 13 |
1 files changed, 7 insertions, 6 deletions
@@ -13,12 +13,13 @@ GNU coreutils NEWS -*- outline -*- This makes rm -rf significantly faster (400-500%) in some pathological cases, and slightly slower (20%) in at least one pathological case. - rm -r deletes deep hierarchies more efficiently. Before, it took O(N^2) - time, now it takes O(N), where N is the depth of the hierarchy. However, - this improvement is not as pronounced as might be expected for very - deep trees, because prior to this change, for any relative name length - longer than 8KiB, rm -r would sacrifice official conformance to avoid the - disproportionate O(N^2) performance penalty. Leading to another improvement: + rm -r deletes deep hierarchies more efficiently. Before, execution time + was quadratic in the depth of the hierarchy, now it is merely linear. + However, this improvement is not as pronounced as might be expected for + very deep trees, because prior to this change, for any relative name + length longer than 8KiB, rm -r would sacrifice official conformance to + avoid the disproportionate quadratic performance penalty. Leading to + another improvement: rm -r is now slightly more standards-conformant when operating on write-protected files with relative names longer than 8KiB. |