# [Haskell-beginners] Calculating Time Complexity

Adrian Neumann aneumann at inf.fu-berlin.de
Mon Jan 26 02:31:48 EST 2009

```With iterative algorithms like the one you posted it's usually
reduced to "count the loops". Here we have two nested for-loops, each
going from 1 to n. In each loop we do some constant amount of work,
so we get (c1*n)*(c2*n) = (c1*c2)*n^2 -> Theta(n^2).

With recursion it's usually a bit more complicated, as you have to
find a closed form. There are however nice lemmata you can use, like
the http://en.wikipedia.org/wiki/Master_theorem

Regards,

Am 26.01.2009 um 01:04 schrieb Matthew J. Williams:

> 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
>
> 			/* 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
>
> 	Sincerely
> 	Matthew J. Williams
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org