analysis of algoritms

Discussion in 'Python' started by Baba, Sep 9, 2010.

  1. Baba

    Baba Guest

    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
     
    Baba, Sep 9, 2010
    #1
    1. Advertising

  2. Baba

    Robert Kern Guest

    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
     
    Robert Kern, Sep 9, 2010
    #2
    1. Advertising

  3. Baba

    Dave Angel Guest

    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
     
    Dave Angel, Sep 9, 2010
    #3
  4. Baba

    Baba Guest

    On Sep 9, 11:22 pm, Alain Ketterlin <-strasbg.fr>
    wrote:
    > Baba <> 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
     
    Baba, Sep 12, 2010
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. ben cohen

    Re: Analysis and Design

    ben cohen, Jun 26, 2003, in forum: VHDL
    Replies:
    0
    Views:
    1,506
    ben cohen
    Jun 26, 2003
  2. Roadie Roger

    Re: Analysis and Design

    Roadie Roger, Jun 28, 2003, in forum: VHDL
    Replies:
    0
    Views:
    1,109
    Roadie Roger
    Jun 28, 2003
  3. jimmij

    algoritms/stl problem?

    jimmij, Jun 19, 2006, in forum: C++
    Replies:
    0
    Views:
    358
    jimmij
    Jun 19, 2006
  4. jimmij

    algoritms/stl problem?

    jimmij, Jun 19, 2006, in forum: C++
    Replies:
    2
    Views:
    269
  5. ssubbarayan
    Replies:
    5
    Views:
    2,394
    Dave Hansen
    Nov 3, 2009
Loading...

Share This Page