1 Aug
2019
1 Aug
'19
4:25 a.m.
If you fully evaluate the list produced by tails, then you're still spending O(n^2) time, because that is just the size of the produced list. But constructing the list and the memory taken by the list is O(n), because most of the lists are shared (https://wiki.haskell.org/Sharing). On 01-08-2019 04:45, Todd Wilson wrote:
It seems that, asymptotically, tails is O(n) while inits is O(n^2) in both time and space (when fully evaluated)