analysis of algoritms
wbrehaut at mcsnet.ca
Fri Sep 10 01:27:37 CEST 2010
On Thu, 09 Sep 2010 18:26:52 -0400, Dave Angel <davea at ieee.org> wrote:
> On 2:59 PM, Baba wrote:
>> 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
>Why are you posting a question about BASIC syntax in a Python forum?
>Python has no such statement, and its close approximations work much
>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
>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
>Incidentally, in some versions of BASIC, 4b and 4c might come after 4d,
>and only be executed n times.
More information about the Python-list