I've already brought this up for Collection, including a bug report.
Some of the viewers of that bug want to keep the property as O(n) for legacy compatibility for Collection users, although that by definition breaks legacy compatibility for pure-Sequence users. Since the property is supposed to be an under-estimate, I agree that we should sacrifice accuracy for speed.