Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re^2: Common Perl Pitfalls

by Joe_ (Beadle)
on Apr 09, 2012 at 23:50 UTC ( #964229=note: print w/ replies, xml ) Need Help??


in reply to Re: Common Perl Pitfalls
in thread Common Perl Pitfalls

Care to elaborate on that "quadratic" comment? How do you figure? I'm not that good with complexity theory, I'm afraid...


Comment on Re^2: Common Perl Pitfalls
Re^3: Common Perl Pitfalls
by JavaFan (Canon) on Apr 10, 2012 at 13:22 UTC
    Care to elaborate on that "quadratic" comment?
    Say you want to delete all elements in the second half of the array. The first N/2 iterations of your loop, no splicing happens. But on the N/2 + 1st iteration, the splicing takes at least N/2 - 1 steps, as that many array elements need to be moved. On the N/2 + 2nd iteration, the splicing takes at least N/2 - 2 steps. In total, you will be moving

    ΣN/2-1i=1(i)

    array elements. If I've done my math correctly, the above sum equals (N2 - 2N + 4)/8. Which means your algorithm runs in Ω(N2) time.

      Wonderful. Thanks for enlightening me...

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://964229]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (5)
As of 2014-09-22 04:15 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (178 votes), past polls