24 Sep
2007
24 Sep
'07
8:20 a.m.
On 9/24/07, Andrew Coppin
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