[Haskell-beginners] Calculating Time Complexity

[Adrian Neumann]

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,

Adrian

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  
> 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
>
> 	Sincerely
> 	Matthew J. Williams
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners

-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 194 bytes
Desc: Signierter Teil der Nachricht
Url : http://www.haskell.org/pipermail/beginners/attachments/20090126/c4a806e2/PGP.bin