Results 1 to 6 of 6

Math Help - Algorithm analysis

  1. #1
    Member
    Joined
    May 2009
    Posts
    109

    Algorithm analysis

    This is regarding the analysis of a basic computer alogrithm.

    It's for a "search sort" alrogrithm. All it does is find the largest number in a list of n elements, places it last and then finds the largest element in the list excluding the last element so each iteration the list has n - 1 elements than before.

    T(n) represents the time complexity for the algorithm and c represents the total for other operations.

    T(n) = (n - 1) + c + (n - 2) + c ... + 2 + c + 1 + c = n(sqr) / 2 - n / 2 + cn

    I can see that this works and that the cn is self explanitory, but how do you get to n(sqr) / 2 - n / 2 part, is there some kind of method or forumla that you work through?

    If you want a slightly more detailed explination and example the same promblem on Analysis of algorithms - Wikipedia, the free encyclopedia. Under "run time complexity" on the frst example it says it can be factored as T6[1/2(n(sqr) + n]. Again I can see it works I just don't understand how you get there.

    This has been driving me mad for about a week. Any help will be appreciated.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    earboth's Avatar
    Joined
    Jan 2006
    From
    Germany
    Posts
    5,830
    Thanks
    123
    Quote Originally Posted by alyosha2 View Post
    ...

    T(n) = (n - 1) + c + (n - 2) + c ... + 2 + c + 1 + c = n(sqr) / 2 - n / 2 + cn

    I can see that this works and that the cn is self explanitory, but how do you get to n(sqr) / 2 - n / 2 part, is there some kind of method or forumla that you work through?

    ...
    1. Re-write the equation:

    T(n)= (n-1)+(n-2)+(n-3)+...+3+2+1+ \underbrace{c+c+c+...+c+c+c}_{\text{n summands}}

    2. Now take the sum

    s=(n-1)+(n-2)+(n-3)+...+3~~~~~+2~~~~~+1

    Now write the sum in reverse order:

    s=1~~~~~~+~~~2~~~~~+~~~3+...+(n-3)+(n-2)+(n-1)

    Add columnwise:

    2s=n+n+n+...+n+n+n=n \cdot n


    Therefore: s = \dfrac12 n^2

    Put all the results together:

    T(n)= (n-1)+(n-2)+(n-3)+...+3+2+1+ \underbrace{c+c+c+...+c+c+c}_{\text{n summands}} = \dfrac12 n^2 + nc
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2009
    Posts
    109
    Oh I see, it's just a variation on the normal sum method.

    thank you.

    Just one more question, why the - n / 2?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    earboth's Avatar
    Joined
    Jan 2006
    From
    Germany
    Posts
    5,830
    Thanks
    123
    Quote Originally Posted by alyosha2 View Post
    Oh I see, it's just a variation on the normal sum method.

    thank you.

    Just one more question, why the - n / 2?
    hmmm ... honestly I'm not quite certain what you mean

    Are you refering to this part of my post?:
    Add columnwise:

    2s=n+n+n+...+n+n+n=n \cdot n

    Therefore: s = \dfrac12 n^2
    If so:

    When you add columnwise the LHS becomes:

    s+s=2s

    and the RHS becomes:

    n\cdot n = n^2

    Since you want to know the value of one s you have to divide by 2. Therefore:

    2s=n^2~\implies~s = \dfrac12 n^2
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2009
    Posts
    109
    no, your post was very clear. I was meaning in the original algorithm.

    T(n) = (n - 1) + c + (n - 2) + c ... + 2 + c + 1 + c = n(sqr) / 2 - n / 2 + cn

    It's the same as yours except it has an extra n / 2 subtracted.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by alyosha2 View Post
    no, your post was very clear. I was meaning in the original algorithm.

    T(n) = (n - 1) + c + (n - 2) + c ... + 2 + c + 1 + c = n(sqr) / 2 - n / 2 + cn

    It's the same as yours except it has an extra n / 2 subtracted.
    Earboth's 2s is equal to n-1 terms each equal to n (he has counted them wrongly), so:

    2s=(n-1)n

    or:

    s=\frac{n^2-n}{2}= \frac{n^2}{2}-\frac{n}{2}

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algorithm Analysis
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: July 1st 2009, 05:02 AM
  2. (Another) Algorithm Analysis
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: June 9th 2009, 02:30 AM
  3. Algorithm Analysis - Big-oh, etc...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 8th 2009, 09:18 AM
  4. Algorithm analysis
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 17th 2009, 08:32 AM
  5. help me to prove this algorithm analysis
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: February 12th 2008, 08:13 PM

Search Tags


/mathhelpforum @mathhelpforum