1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Algorithm Efficiency

  1. Mar 25, 2017 #1
    1. The problem statement, all variables and given/known data
    Consider the ##xyzzy## algorithm below. This algorithm takes a linear collection (e.g., a list or array) of size ##n## as an argument (i.e., as the input to the algorithm) and produces no return value (i.e., has no output, but might alter the linear collection). Note that the implementation of the ##xyzzy## algorithm requires that you use the unspecified operations ##foo, bar## and ##qux ~-## though you don’t know what these operations do, you can assume they all take the same amount of time to complete. You don’t need to know anything else about them to answer the question below.

    upload_2017-3-25_22-48-47.png

    If you were attempting to formally analyze the efficiency of this algorithm, which operation (or operations) from the set ##\{foo, bar, qux\}## would be the best choice for the model of computation?

    2. Relevant equations
    n/a

    3. The attempt at a solution

    I think the answer is ##qux## because its conditional (while loop) increments ##k## while the loops containing the other operations do not increment their iteration counters; that is, ##j = j * 2## keeps ##j## at ##0## and ##i = i##++ doesn't increment ##i## because the assignment occurs before the ++, so ##i## is perpetually assigned ##0;## rather, ##i =## ++##i## would increment ##i.##

    Can someone please verify if I'm approaching this correctly and perhaps lend more insight into what the question's asking? Thanks!
     
  2. jcsd
  3. Mar 25, 2017 #2
    These are nested loops.

    "foo" will be executed "n" times.
    "bar" will be executed "n*log2(n)" times.
    "qux" will be ...

    The question is awkwardly posed, but it seems to be asking for the functions that influence the efficiency of xyzzy. If that's the case, then all three should be selected.
    That said, those functions do not have equal effect of the efficiency of xyzzy. The one in the inner-most loop (qux) will be executed "n" times more than "bar".
     
  4. Mar 25, 2017 #3
    But notice that ##i## and ##j## are initialized as ##0## then 'updated' as follows: ##j = j * 2## and ##i = i##++. Therefore, their loops (the two outermost loops) would execute indefinitely. The innermost loop is the only one that properly increments its iteration counter. I'm wondering what bearing this observation has on answering the question...
     
  5. Mar 25, 2017 #4
    The outer loop is: i=0;while(i<n):;i=i++. I take the i=i++ to be equivalent to i=i+1 or (in C) i++. So that loop will run "n" times (not indefinitely).
    But you are right. That second loop has a bug in it. It is given as: j=0;while(j<n):;j=j*2. So j will follow the sequence 0, 0, 0, ...
    So, given this bug, the answer is that none of these functions need to be included in the analysis. In n<1, then xyzzy will return without executing any of them. If n>=1, then xyzzy will never return.

    However, I do not believe that is what was intended. I believe that second loop is supposed to be: j=1;while(j<n):;j=j*2. So j will follow the sequence 1, 2, 4, 8, 16, ... for as along as it is less than n.
     
  6. Mar 25, 2017 #5
    ##i## = ##i##++ increments the RHS ##i## after its assignment to the LHS ##i.## The correct syntax is either ##i =## ++##i## (increments before assignment), or just ++##i## or ##i##++. Source: http://stackoverflow.com/questions/24853/what-is-the-difference-between-i-and-i. ##i = i##++ assigns RHS ##i## (i.e., ##0##) to LHS ##i## before RHS ##i## is incremented, so ##i,## just like ##j,## is perpetually assigned ##0.##
     
    Last edited: Mar 26, 2017
  7. Mar 26, 2017 #6
    If you're talking about C, that's certainly true. I wasn't assuming that this pseudo-code was borrowing from C that closely.
     
  8. Mar 26, 2017 #7
    Good point. However, if the question wants us to make the observation that ##i## and ##j## are perpetually assigned 0, how would that affect your answer? I'm still unsure about how to answer the question...
     
  9. Mar 26, 2017 #8
    It j stays at zero, the algorithm is broken. If i stays at zero, the algorithm is broken - in almost the same way. If both are broken, it's very similar to j being broken alone - since that will be the loop you'll get stuck in.
     
  10. Mar 26, 2017 #9
    I think you are right, though, in that they meant to initialize ##j## as ##1## and have ##i## increment in each of its loop's iterations, in which case:

    ##\rm{foo}## is executed ##n## times
    ##\rm{bar}## is executed ##n \log_2 n## times
    ##\rm{qux}## is executed ##n^2 \log_2 n## times

    The worst-case time-complexity of the algorithm is ##O(n^2 \log_2 n),## which is the same complexity as the innermost loop, so I guess ##\rm{qux}## is the answer? (Though the ##\rm{qux}## loop wouldn't have this complexity without the ##\rm{foo}## and ##\rm{bar}## loops...) This question is for school and I honestly have no idea how to answer it, it seems awkwardly posed.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Algorithm Efficiency
  1. Prove an Algorithm (Replies: 1)

  2. Division algorithm (Replies: 5)

  3. Efficiency of a hill (Replies: 7)

  4. Efficiency PowerPlant (Replies: 4)

  5. Efficiency of a ramp (Replies: 3)

Loading...