Author: Stan Eisenstat
Subject: Re: [Cs323] Pruning follow-up
Date: Saturday, 07 Nov 2020, 07:50:35

    > Message Posted By: Unknown
    >
    > When adding each old entry into new table, we need to recursively add its
    > prefix into the new table as well, so isn't that o(n^2)?

The prefix of every string in the new table must be in
that table, but you need not use recursion to achieve
this goal.

And recursion does not imply that pruning runs in
time quadratic in the size of the new table.

--Stan-