analysis of algoritms

[Alain Ketterlin]

Baba <raoulbia at gmail.com> writes:

> 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

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.