analysis of algoritms

[Robert Kern]

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