Results 1 to 4 of 4

Math Help - Algorithm Analysis

  1. #1
    Member
    Joined
    May 2009
    Posts
    107

    Algorithm Analysis

    This is about an Merge Sort computer algorithm.
    Firstly here's the full thing.

    <br />
T(n) = 2T(\frac{n}{2}) + 2n - 1 = 2(2T(\frac{n}{4}) + 2\frac{n}{2} - 1 ) + 2n - 1<br />

    <br />
= 2^2 T(\frac{n}{2^2}) + 2n - 2 + 2n - 1<br />

    <br />
=2^kT(\frac{n}{2^k}) + 2n - 2^k ... 2n - 2 + 2n - 1<br />

    couldn't figure out how to get log as an exponent

    <br />
2(to the log of n)T(\frac{n}{2(to the log of n)} + 2(to the log of n - 1) + ... + 2n - 2 + 2n - 1<br />

    <br />
= n + 2n \log{n} - 2(to the log of n) + 1 = 2n \log{n} + 1 = O(n \log{n})<br />


    I asked a question about this before and got a good answer that made me realise that what was going on was recursion. Now, to my understanding all recusion needs a base case. In this instance I'm thinking that this would be T(1) as this would mean that there would be no sorting to do. Does this mean that T(1) = 1? as in the last 3rd to last part where 2 to the log on n X T(n / 2 to the log of n) is reduced to n?

    Also for each level of recursion that you go down I can understand that you would have another 2n - 1 (where n is the reduced input) but I'm having a hard time trying to see how this works as giving the 2n - 2 to log n -1 ... .

    And lastly, and I'm quite sure this is linked to the above question, where does the + 1 come from in the last two but one parts?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by alyosha2 View Post
    I asked a question about this before and got a good answer that made me realise that what was going on was recursion. Now, to my understanding all recusion needs a base case. In this instance I'm thinking that this would be T(1) as this would mean that there would be no sorting to do. Does this mean that T(1) = 1? as in the last 3rd to last part where 2 to the log on n X T(n / 2 to the log of n) is reduced to n?
    In when n=1 there is nothing to do T(1)=0 , though you might be happier hand working the case n=2 to find the value of T(2).

    For the rest of your post could you please reorganise it so that it is easier to see what your questions are and please clean up you LaTeX.

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2009
    Posts
    107
    Quote Originally Posted by CaptainBlack View Post
    In when n=1 there is nothing to do T(1)=0 , though you might be happier hand working the case n=2 to find the value of T(2).

    For the rest of your post could you please reorganise it so that it is easier to see what your questions are and please clean up you LaTeX.

    CB
    Cleaned up LaTeX







    <br />
2^{log\;n-1}T(\frac{n}{2^{log\;n-1}}) + 2^{log\;n-1} + ... + 2n - 2 + 2n - 1<br />

    <br />
= n + 2n \log{n} - 2^{log\;n-1} + 1 = 2n \log{n} + 1 = O(n \log{n})<br />


    Ok, what I'm trying to get at is understadning each step of the expresion as it relates to the merge sort algorithm.

    Merge sort takes an array of n number of inputs and then keeps dividing them untill they reach single inputs it then arranges them into sorted arrays by first adding single inputs to make arrays of two then two to make arrays of four etc. until you have one sorted array.

    so if T(n) represent the time complexity of the algorithm then

    <br />
T(\frac{n}{2}) + T(\frac{n}{2}) + mergetime <br />

    mergetime is 2n - 1

    there a much better(more mathmatical) description on wikipedia

    Merge sort - Wikipedia, the free encyclopedia

    the point where my understading begins to slip is on the second line. I can see that the 2squared before the T and in the denominator result from multiplying out the brackets and the 2n also. But at this point I can't see what part of the algorithm 2n - 2 is representing. I can't make the link.

    This then becomes represented as - 2 to the power of k in the next part and then log of n in the next part. But I think I'll understand these when I understand where the original - 2 comes from(or rather waht it represents).

    And lastly how do you end up with n in the begining of the first part of the last line as well as the + 1 at the end.

    I hope that's clear enough, as I'm sure you can tell I'm a bit confused.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2009
    Posts
    107
    No one has any ideas?

    Is the question too vauge or confused?

    I'd appreciate help with this if anyone can.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. (Another) Algorithm Analysis
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: June 9th 2009, 02:30 AM
  2. Algorithm analysis
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: June 4th 2009, 05:29 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