[Haskell-cafe] Complexity question
Roel van Dijk
vandijk.roel at gmail.com
Mon Sep 24 12:42:09 EDT 2007
On 9/24/07, Matthew Brecknell <haskell at brecknell.org> wrote:
> I believe Bas is correct, though it might be worth elaborating on what
> he means by "worst case".
I think worst case can be interpreted as meaning: all rows have length c.
Most of the "work" consists of applying (:) if we ignore pattern
matching. The number of applications of (:) can be calculated with the
following function:
-- Number of rows after transposing plus the sum of the length of those rows
numApps xss = let t = transpose xss
in (length t) + sum (map length t)
Consider:
-- 3 rows, max 10 columns
transpose [ "1234567890"
, "123"
, "123"
]
> ["111", "222", "333", "4", "5", "6", "7", "8", "9", "0"]
26 applications of (:)
The number of applications of (:) is greatest when all lists have equal length.
More information about the Haskell-Cafe
mailing list