analysis of algoritms

[Wayne Brehaut]

On Thu, 09 Sep 2010 18:26:52 -0400, Dave Angel <davea at ieee.org> wrote:

>  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
REM And the vuitally important:
  4e   GOTO 4b

But, as Robert noted, this is undoubtedly "pseudocode" rather than
BASIC. Pity it's not Python-oriented pseudocode...

>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