[Haskell-cafe] Complexity question
Bas van Dijk
v.dijk.bas at gmail.com
Mon Sep 24 04:20:00 EDT 2007
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:
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.
More information about the Haskell-Cafe