Calculating Time Complexity
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
On Mon, Jan 26, 2009 at 01:04, Matthew J. Williams < matthewjwilliams1@googlemail.com> wrote:
Dear all,
In general terms, how would one calculate the time complexity of a given algorithm?
I would count most significant operations. The result is Theta(n^2) (see http://en.wikipedia.org/wiki/Big_O_notation for definition of Big Theta notation). 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
Christopher Skrzętnicki
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
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
participants (4)
-
Adrian Neumann -
Brent Yorgey -
Krzysztof Skrzętnicki -
Matthew J. Williams