Posted by hussein on July 30, 1999 at 16:03:48:
hi
just thought i should mention these before i totally forget ...
1. on monday, Kevin brought up the issue of whether or not we perform path compression on the last node ... it happens that the text is unclear in its explanation ... however if you read through the code and follow the example, its quite clear that we DO perform path compression on the last node as well
2. on thursday, Pete asked why bubble sort had a best case that was in O(n^2) instead of O(n). Well, this argument can be extended by prepending any algorithm with a routine that checks if the list is sorted (and that is in O(n)) ... if we use flags, we have to be careful where we put such flags since including them within an algorithm may increase the number of comparisons, albeit comparisons of flags and not elements ...
---
hussein