analysis of algoritms

[Dave Angel]

  On 2:59 PM, Baba wrote:
> Hi
>
> In below code "the outer loop test in step 4 will execute ( n + 1 )
> times (note that an extra step is required to terminate the for loop,
> hence n + 1 and not n executions), which will consume T4( n + 1 )
> time." (from http://en.wikipedia.org/wiki/Analysis_of_algorithms)
>
> 1    get a positive integer from input
> 2    if n>  10
> 3        print "This might take a while..."
> 4    for i = 1 to n
> 5        for j = 1 to i
> 6            print i * j
> 7    print "Done!"
>
> Why does step 4 execute n+1 times? what is the exta step mentioned
> above
>
> tnx
> Baba
>
Why are you posting a question about BASIC syntax in a Python forum?  
Python has no such statement, and its close approximations work much 
differently.

If you really want an abstract answer, then you should be decomposing 
those BASIC statements into smaller atoms.  The for statement is 
composed of at least three "atoms", one of which is probably executed 
n+1 times.

A BASIC for statement   for i=1 to n
decomposes into approximately:

4a,   i = 1
4b    compare i to n
4c    skip if greater
       5, 6 do some stuff
4d     increment i

Note that the increment happens after steps 5 and 6, but it's part of line 4

Also note that the exact details depend thoroughly on the brand and 
version of BASIC, there being at least 60 versions out there.  For 
example, I can think of at least three cases for what i will equal on 
line 7.

Incidentally, in some versions of BASIC, 4b and 4c might come after 4d, 
and only be executed n times.

DaveA