Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > analysis of algoritms

Reply
Thread Tools

analysis of algoritms

 
 
Baba
Guest
Posts: n/a
 
      09-09-2010
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
 
Reply With Quote
 
 
 
 
Robert Kern
Guest
Posts: n/a
 
      09-09-2010
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

 
Reply With Quote
 
 
 
 
Dave Angel
Guest
Posts: n/a
 
      09-09-2010
On 2:59 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
>
> 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

 
Reply With Quote
 
Baba
Guest
Posts: n/a
 
      09-12-2010
On Sep 9, 11:22*pm, Alain Ketterlin <(E-Mail Removed)-strasbg.fr>
wrote:
> Baba <(E-Mail Removed)> 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." (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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Evaluating static analysis and Dynamic analysis tools for C/C++ ssubbarayan C Programming 5 11-03-2009 12:50 AM
algoritms/stl problem? jimmij C++ 2 06-19-2006 06:55 PM
algoritms/stl problem? jimmij C++ 0 06-19-2006 04:28 PM
Re: Analysis and Design Roadie Roger VHDL 0 06-28-2003 05:01 AM
Re: Analysis and Design ben cohen VHDL 0 06-26-2003 04:18 PM



Advertisments