Re: Analyzing Alg. Runtime

"Brad" <yoda_132002@xxxxxxxxxxx> writes:

//This is a homework assignment so I am not looking for the answer,
but possibly an explination of how to figure it out.


I am given the algorithm (on line 2 it is suppose to be "i (less than
or equal to) n")
GSSSum
1. sum = 0;
2. for (i = 0; i < n; ++i) {
3. prod = 1;
4. for (j = 0; j < i; ++j)
5. prod = prod * x;
6. sum = sum + prod; }
7. return sum;

(x is a given value and n is non-negative integer)
I am suppse to analyze the run time for each line and then Compute the
total run time.
This is what i came up with. Not sure how right it is:
1. 1
2. n+1
3. n
4.
5.
6.
7. 1

Could someone let me know if I'm on the right track for the ones I
filled in an give some hints for the others.

Well, you can start this way. I'd rather start from the inside out.

The inner loop, line 5 is executed i times.

The outer loop, lines 3-6 are executed n times, with i going from 0 to
n-1 (or n if you replace < by <= on line 2).

So the total number of times line 5 is executed is 0+1+2+...+(n-1) (or n).
this sum is n*(n-1)/2 = ½n²-½n

If you want to give the result line by line, we get (with < in line 2):

1. 1
2. n
3. n
4. ½n²-½n
5. ½n²-½n
6. n
7. 1


Now, the for lines you could consider you execute them n+1 times, but
they are composed really of several instructions.

for(i=0; 1
i<n; n+1
++i){ n

}

so they are executed n+1 times only partially. In general, we don't
enter in these details, only if you want to count the exact number of
microprocessor instructions or cycles. But then, compiler
optimizations and processor pipelines may change entirely the way how
the code is executed. For example, the compiler "unroll" the loop, so
doesn't have to test for i<n and jump so often. It could start by
testing whether i+8<n, and copy 8 times the body of the loop separated
by ++i (or just with literal offsets).

Like:

for(i=0;i+8<n;i+=8){
prod = 1; for (j = 0; j < i+0; ++j) prod = prod * x; sum += prod;
prod = 1; for (j = 0; j < i+1; ++j) prod = prod * x; sum += prod;
prod = 1; for (j = 0; j < i+2; ++j) prod = prod * x; sum += prod;
prod = 1; for (j = 0; j < i+3; ++j) prod = prod * x; sum += prod;
prod = 1; for (j = 0; j < i+4; ++j) prod = prod * x; sum += prod;
prod = 1; for (j = 0; j < i+5; ++j) prod = prod * x; sum += prod;
prod = 1; for (j = 0; j < i+6; ++j) prod = prod * x; sum += prod;
prod = 1; for (j = 0; j < i+7; ++j) prod = prod * x; sum += prod; }
switch (n-i){
case 7: prod = 1; for (j = 0; j < i; ++j) prod = prod * x; sum += prod; ++i;
case 6: prod = 1; for (j = 0; j < i; ++j) prod = prod * x; sum += prod; ++i;
case 5: prod = 1; for (j = 0; j < i; ++j) prod = prod * x; sum += prod; ++i;
case 4: prod = 1; for (j = 0; j < i; ++j) prod = prod * x; sum += prod; ++i;
case 3: prod = 1; for (j = 0; j < i; ++j) prod = prod * x; sum += prod; ++i;
case 2: prod = 1; for (j = 0; j < i; ++j) prod = prod * x; sum += prod; ++i;
case 1: prod = 1; for (j = 0; j < i; ++j) prod = prod * x; sum += prod; ++i;
case 0: }

(it might more probably do that for inner loops than outer loops, but
you get the idea).


So i would just count n for line 2.



--
__Pascal Bourguignon__ http://www.informatimago.com/
Kitty like plastic.
Confuses for litter box.
Don't leave tarp around.
.

Relevant Pages

  • Re: Interesting article by Randall Hyde
    ... > execute the number of times specified by the expression. ... restatement of a whileloop, ... > where they've tried to specify the semantics better. ... > the compiler takes care of everything for them and they ...
    (comp.lang.asm.x86)
  • Safe multithreading in ASP.Net
    ... Code in global.asx Application_start subroutine, ... Dim emails As New ForumEmail ... Do While ContinueNotify 'boolean value set to True so loop will continue ... the thread still continues to execute. ...
    (microsoft.public.dotnet.framework.aspnet)
  • RE: What is the difference between for..if, case statements, do..while
    ... ElseIf Then ... It can not execute both This and That or any ... Loop Until ... How does one decide which programming construct to use. ...
    (microsoft.public.excel.programming)
  • Re: What is the difference between for..if, case statements, do..while
    ... ElseIf Then ... It can not execute both This and That or any ... Loop Until ... Do while an loop until cause you to loop throgh the same st of instructions ...
    (microsoft.public.excel.programming)
  • Re: Why not a Python compiler?
    ... compiler know what object is bound to the name `xrange` when that loop ... solution is for the compiler to create something like this pseudo-code: ... execute unoptimized normal loop at Python speed ...
    (comp.lang.python)