[Haskell-cafe] Complexity question

[Roel van Dijk]

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.