Calculating Time Complexity

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Calculating Time Complexity

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

Reply | Threaded
Open this post in threaded view
|

Calculating Time Complexity

Krzysztof Skrzętnicki
On Mon, Jan 26, 2009 at 01:04, Matthew J. Williams <
[hidden email]> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20090126/6e10550a/attachment-0001.htm
Reply | Threaded
Open this post in threaded view
|

Calculating Time Complexity

Adrian Neumann
In reply to this post by Matthew J. Williams
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
> [hidden email]
> 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
Reply | Threaded
Open this post in threaded view
|

Calculating Time Complexity

Brent Yorgey-2
In reply to this post by Matthew J. Williams
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