Re: An informal introduction to O(N) notation

[jryan]

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..$#a-1) {
    for (0..$#a-1-$i) {
        ($a[$_],$a[$_+1]) = ($a[$_+1],$a[$_])
            if ($a[$_+1] < $a[$_]);
  }
}

# O(n log(n))
for my $i (0..$#a-1) {

    # looping over already-sorted items is not needed
    for (0..$#a-1-$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 :)

[fruiture]

Sorry, but that's nonsense. If you say that searching for an element in an unsorted list becomes O(log n) if you stop searchng after you've found the element, you actually say that every element in a list is located among it's first log(n) elements, (where n is the length of the list) and everybody knows that the elements of a list reside within the whole list, that's their definition. So your assumption would be true if there existed some "a" and some "n" for which log_an = n, but there is no such a.

Btw.: O(n) does not mean that you don't stop searching a list after you've found the thing you're looking for, of course you do that, but you must expect that you have to search the whole list if the element you're looking for is the last element or not in the list.

But you _can_ make list search O(log n) by keeping the list sorted and then doing binary search.

--
http://fruiture.de

[MarkM]

Your bubble sort examples for O(n) and O(n log n) are the same (the first needs to be un-optimized). Also, I believe the optimized bubble sort is O(n²/2), not O(n log n).

For your second suggestion, loops that can break out early are still O(n) in the worst case, as no guarantee can be made that all other elements will not be considered before the target element.

[dws]

It should be noted that many algorithm's O time can be reduced.

You may be getting "best case" and "worst case" mixed up. Clever short-circuits in implementations of algorithms often increase the best case, but only if the data behaves certain ways. There are usually mixes of data that defeat the short-cuts. O() is about worst-case behavior.

[demerphq]

It should be noted that many algorithm's O time can be reduced.

True. But then it isnt the same algorithm. :-) Also care in implementation can make one version of an algorithm outperform another. For instance I think you will find that

my $tmp;
for my $i (0..$#a-1) {
    # looping over already-sorted items is not needed
    for (0..$#a-1-$i) {
        if ($a[$_+1] < $a[$_]) {
          $tmp=$a[$_];
          $a[$_]=$a[$_+1];
          $a[$_+1]=$tmp;
        }
    }

}

Is slightly faster than your version. :-) Its funny actually but Knuth discusses this exact issue as a justification as to why he used MIX instead of a high level programming language. People have a tendency to write code in as few characters as possible. (Perl gives an opportunity to take this way beyond reasonable so we can ignore that stuff.) However very often the constructs that take the least space for the human result in the most code being excuted. To take this further for a while I was working on implementing a bunch of the AoP algorithms in perl. Some of them are not feasable as perl doesnt allow low enough operations. I believe that you will find one of the linear search algorthms (you'd never think this would be tricky) is unimplementable in perl to be more efficient than the others (even though in MIX and assembler it is).

Also IIRC the following minor change makes Bubblesort get even faster

my $tmp;
my $swapped;
for my $i (0..$#a-1) {
    $swapped=0;
    # looping over already-sorted items is not needed
    for (0..$#a-1-$i) {
        if ($a[$_+1] < $a[$_]) {
          $tmp=$a[$_];
          $a[$_]=$a[$_+1];
          $a[$_+1]=$tmp;
          $swapped=1;
        }
    }
    last unless $swapped;
}

As it allows it to bail once the list is sorted. (Atually you could probably be clever and not use one of the extra variables, although only if undef isnt legal in the data being sorted.)

update fixed typo in the second version. thanks jryan. :-)

--- demerphq
my friends call me, usually because I'm late....