This extremely sloppy upper bound can be derived by noting, in the worst case a d-digit radix-r number has d ancestors, and each ancestor requires r space. Given n numbers, the total space used is O(rdn).
This upper bound is sloppy because it doesn't account for ancestor sharing among numbers. It also doesn't account for relatively unique numbers, which will have fewer than the d maximum necessary ancestors.
This page last modified on 24 January 2006.