[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,
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
More information about the Beginners
mailing list