Algorithm Efficiency

[emeraldskye177]

Homework Statement

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.

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?

Homework 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!

 

[.Scott]

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".

 

[emeraldskye177]

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".

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...

 

[.Scott]

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...

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.

 

[emeraldskye177]

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.

$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.$

 

[.Scott]

$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.$

If you're talking about C, that's certainly true. I wasn't assuming that this pseudo-code was borrowing from C that closely.

 

[emeraldskye177]

If you're talking about C, that's certainly true. I wasn't assuming that this pseudo-code was borrowing from C that closely.

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...

 

[.Scott]

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...

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.

 

[emeraldskye177]

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.

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.