[Haskell-cafe] Complexity question

[Andrew Coppin]

Matthew Brecknell wrote:
> 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.

On the other hand, my program needs the entire transposed list, so... ;-)