June 10, 2017
8:26 p.m.
On 2017-06-11 00:13, David Mertz wrote:
Bernardo Sulzbach posted a much prettier version than mine that is a bit shorter. But his is also somewhat slower (and I believe asymptotically so as the number of equal elements in subsequence goes up). He needs to sum up a bunch of 1's repeatedly rather than do the O(1) `len()` function.
Constructing a list from an iterator of size N is in O(N). Summing N elements is in O(N). I don't think it is asymptotically slower, just slower because of implementation details. -- Bernardo Sulzbach http://www.mafagafogigante.org/ mafagafogigante@gmail.com