On 9/9/10 4:39 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
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
--
http://mail.python.org/mailman/listinfo/python-list
