[Haskell-cafe] Complexity question

[Matthew Brecknell]

Andrew Coppin:
> Anybody happen to know what the time complexity of "transpose" is?

Bas van Dijk:
> The worst case time complexity is O(r*c) where 'r' are the number of
> rows and 'c' are the number of columns.

I believe Bas is correct, though it might be worth elaborating on what
he means by "worst case".

Because transpose is quite lazy, it need not necessarily result in a
quadratic time complexity on every use. For a trivial example,
(sum . map head) could be replaced with (sum . head . transpose),
without affecting the linear time complexity. In fact, because of its
laziness, you can pretty much ignore applications of transpose when
working out *asymptotic* complexities, because transpose will never
do any more damage than the functions which consume its result.

Of course, whether you do ignore it will depend on how much you care
about the constant factor.