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@haskell.org http://www.haskell.org/mailman/listinfo/beginners