Algorithm Analysis?

Discussion in 'OT Technology' started by hdot, Oct 14, 2008.

  1. hdot

    hdot New Member

    Joined:
    Jan 25, 2007
    Messages:
    10,758
    Likes Received:
    0
    Location:
    Texas
    This is for my computer science class. For my next assignment I've got some questions similar to the following, and I'm having trouble figuring out how I would go about doing them, exactly.

    Question 1:
    Algorithm A executes 10n log n operations while Algorithm B executes n 2 operations. Determine the minimum integer value n 0 such that A executes fewer operations than B for n >= n 0.

    Is there a way to set up equations to compare the two? Or is there something else to it that I'm not seeing? There are no examples similar to this in my book so I'm kind of lost as far as direction..

    A point in the right direction is all I'm looking for. Thanks..
     
  2. CodeX

    CodeX Guest

    Do you have a graphing calculator or mathmatica?

    Graph n^2 against 10n*logn, find the point that they cross
     
  3. hdot

    hdot New Member

    Joined:
    Jan 25, 2007
    Messages:
    10,758
    Likes Received:
    0
    Location:
    Texas
    Ahh.. Yes, thank you! I knew it would be something with finding their intersections but I was unsure of how to do it.

    Would the same process work for this one?

    b)The number of operations executed by algorithms A and B is 8n log n and 2n^2, respectively. Determine n0 such that A is better than B for n >= n0.



    And so forth..? I've got a couple of these to answer and want to make sure .. The wording of them is what mixes me up.
     
  4. euphoric

    euphoric Who else here has some pants? Moderator

    Joined:
    May 22, 2002
    Messages:
    32,383
    Likes Received:
    0
    Location:
    Austin, Texas
    i wish my algorithims class was that easy :wtc:
     
  5. hdot

    hdot New Member

    Joined:
    Jan 25, 2007
    Messages:
    10,758
    Likes Received:
    0
    Location:
    Texas
    :rofl:

    This isn't my algorithms class .. That's next semester. I just wish my teacher did more than go through slides and tell us to read the book, then assign stuff that was not explained by the book or the slides :greddy:
     
  6. quzer

    quzer New Member

    Joined:
    Nov 9, 2003
    Messages:
    206
    Likes Received:
    0
    this is like calc 1 stuff lol
    all you gotta do is solve this equation:

    8n log(n) = 2n^2
     
  7. hdot

    hdot New Member

    Joined:
    Jan 25, 2007
    Messages:
    10,758
    Likes Received:
    0
    Location:
    Texas
    Wow .. I should be punched in the face.

    Thanks bro.

    :h5:
     
  8. quzer

    quzer New Member

    Joined:
    Nov 9, 2003
    Messages:
    206
    Likes Received:
    0
    actually after messing around with it, it's just better to plot two different lines and find the intersection, the solution for that equation is not very simple!

    you can however simplify it to 4*log(n) = n

    n = 8.613169456
     
  9. hdot

    hdot New Member

    Joined:
    Jan 25, 2007
    Messages:
    10,758
    Likes Received:
    0
    Location:
    Texas
    Here's my next problem .. Got a little confused here about calculating run times.

    Analyze its worst-case running time and express it in “Big Oh” notation.

    Algorithm [FONT=&quot]Foo[/FONT](a, n):
    Input: two integers, a and n
    Output: a^n
    k [FONT=&quot]← [/FONT]0
    b [FONT=&quot]←[/FONT] 1
    while k < n do
    k [FONT=&quot]←[/FONT]k + 1
    b [FONT=&quot]←[/FONT]b * a
    end while
    return b


    I know that I need to count how many times each step will be performed, but how do I calculate it in terms of n? It looks to me like the steps inside the while loop will run (N+1) times, but how do I calculate the rest of the steps? Any help would be great..
     
  10. Limp_Brisket

    Limp_Brisket New Member

    Joined:
    Jan 2, 2006
    Messages:
    48,422
    Likes Received:
    0
    Location:
    Utah
    the stuff in the loop will run n times, so if you consider b<- b*a to be your basic operation then then runtime in terms of n would be t(n) = n. that would be your worst case and you every case as it would be the same everytime depending on n. so you could say the big oh runtime is O(n) which means that the complexity category of this algorithm is <= n
     
  11. hdot

    hdot New Member

    Joined:
    Jan 25, 2007
    Messages:
    10,758
    Likes Received:
    0
    Location:
    Texas
    hm.. I see what you did, and it makes sense. However, I've got other problems that are very similar and I'm having difficulty understanding the process. Perhaps I can post it, break down what I think is correct and you can guide me through it? Here's the next algorithm (it performs the same task, so clearly the runtime is intended to be different)..

    Algorithm [FONT=&quot]Bar [/FONT](a, n):
    [FONT=&quot]Input[/FONT][FONT=&quot]: two integers, a and n[/FONT]
    [FONT=&quot]Output: ?[/FONT]
    [FONT=&quot]k ← n [/FONT]
    [FONT=&quot]b ← 1[/FONT]
    [FONT=&quot]c ← a[/FONT]
    [FONT=&quot]while k > 0 do[/FONT]
    [FONT=&quot]if k mod 2 = 0 then[/FONT]
    k [FONT=&quot]←[/FONT]k / 2
    c [FONT=&quot]←[/FONT]c * c
    else
    k [FONT=&quot]←[/FONT]k – 1
    b [FONT=&quot]←[/FONT]b * c
    end if
    end while
    return b
    Problem 3:

    Since k = n, I will assumed that everything within the while loop will again run in O(n) time, based on what you said before .. The basic operation then would be the b <- b*c, correct? But if that's the case, how would you go about determining how many times that process is run? The if/else statement is what confuses me on this one. Since the b <-b*c is dependent on the outcome of the if/else, how would I determine the runtime of that function? Perhaps I should research this whole Big Oh thing a bit further?
     

Share This Page