[Haskell-beginners] Calculating Time Complexity
Brent Yorgey
byorgey at seas.upenn.edu
Mon Jan 26 07:41:41 EST 2009
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
More information about the Beginners
mailing list