It should be noted that many algorithm's O time can be reduced. For instance, many O(n^2) algorithms can be reduced to O(n log(n)) by finding a way to cut the inner loop short. A famous example is bubblesort:
# O(n^2)
for my $i (0..$#a1) {
for (0..$#a1$i) {
($a[$_],$a[$_+1]) = ($a[$_+1],$a[$_])
if ($a[$_+1] < $a[$_]);
}
}
# O(n log(n))
for my $i (0..$#a1) {
# looping over alreadysorted items is not needed
for (0..$#a1$i) {
($a[$_],$a[$_+1]) = ($a[$_+1],$a[$_])
if ($a[$_+1] < $a[$_]);
}
}
O(n) algorithms that involve a search via a loop can sometimes be
reduced from O(n) to O(log(n)) by breaking out of the loop once a
"result" is found:
# O(n)
my $truestatus;
foreach my $item (@list) {
$truestatus = 1 if (some_condition);
}
# O(log(n))
my $truestatus;
foreach my $item (@list) {
# if some_condition is going to be valid for at least one $item in
# @list, then the limit of the average runtime will approach
# O(log n).
if (some_condition) {
$truestatus = 1;
last
}
}
Of course, the secret is to know where to apply these optimizations, which is often harder than it seems :)
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
 a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
Outside of code tags, you may need to use entities for some characters:

For: 

Use: 
 &   & 
 <   < 
 >   > 
 [   [ 
 ]   ] 
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.

