[Haskell-beginners] Calculating Time Complexity

[Brent Yorgey]

On Mon, Jan 26, 2009 at 12:04:48AM +0000, Matthew J. Williams wrote:
> Dear all,
>
> In general terms, how would one calculate the time complexity of a given 
> algorithm? Feel free to make use of my pseudo code in your answer:
>
> 			/* input:
> 			2-D array A of size n by n
> 			   output: a number max */
> 			Max := 0
> 			For i := 1 to n
> 			  sum := 0
> 			  For j := 1 to n
> 			    sum := sum + A[i][j]
> 			  End for
> 			  If sum > max then max := sum
> 			End for
> 			   Output max

This being a Haskell mailing list, I couldn't help also translating
this code into simple Haskell:

  maxRowSum :: (Num a, Ord a) => [[a]] -> a
  maxRowSum = maximum . map sum

In this form it's a little harder to see how many operations are being
done (and hence the time complexity), however!

-Brent