analysis of algoritms

[Baba]

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

 

[Robert Kern]

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

You may wish to ask the question on the associated Discussion page for that
article. Hopefully the author of that statement will notice it there. They are
almost certainly not here.

That said, an extra step is required because a real implementation of that
algorithm in a language will create a variable `i` initialized to 1, increment
it each round through the loop, and check it before running the loop. When the
check indicates that it equals n + 1 (not n!) it will exit the loop. That
particular pseudocode notation hides that detail. Of course, there are ways to
implement that pseudocode that do not require the last check, but none of real
importance.

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco

 

[Dave Angel]

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

 

[Baba]

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." (fromhttp://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

In "the outer loop test [...]", the important word is _test_. Line 4 has
to test the value of i against n, which results in true n times and in
false once (where it jumps to instruction 7).

Note that this would be true even with python loops using range(n) or
xrange(n), where the test is not an integer comparison.

(Note also how this last remark tries to avoid complete off-topic-ness
of this discussion in this group

-- Alain.

Hi Alain

Thanks for the explanation!

Baba