[Haskell-cafe] Complexity question
andrewcoppin at btinternet.com
Mon Sep 24 12:27:33 EDT 2007
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... ;-)
More information about the Haskell-Cafe