11 May
2004
11 May
'04
12:02 a.m.
On Mon, 2004-05-10 at 12:46, Wolfgang Jeltsch wrote:
Anyways, 'toList' will still be O(m) where m = number of subtrees. Moreover, I hardly expect more that O(n) empty subtrees in a sequence.
It's theoretically possible that m is much larger than n. But since you need at least O(m) time to construct a Seq with m subtrees¹) the total time of Seq construction plus conversion is asymptotically the same as without full lazyness.
If we're talking about "theoretically possible": it's also possible that somebody converts to a list multiple times, or converts multiple subtrees to lists. Carl Witty