[Haskell-cafe] Complexity question

[Bas van Dijk]

On 9/24/07, Andrew Coppin <andrewcoppin at btinternet.com> wrote:
> Anybody happen to know what the time complexity of "transpose" is?

Looking at the definition of 'transpose' in:
http://darcs.haskell.org/libraries/base/Data/List.hs:

transpose               :: [[a]] -> [[a]]
transpose []             = []
transpose ([]   : xss)   = transpose xss
transpose ((x:xs) : xss) = (x : [h | (h:t) <- xss]) : transpose (xs :
[ t | (h:t) <- xss])

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

regards,

Bas