On 9/24/07, Andrew Coppin <[EMAIL PROTECTED]> 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
