On 9/24/07, Matthew Brecknell
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.