Feb 21, 2008 at 4:28 PM
Edited Feb 21, 2008 at 4:30 PM

Hi there,
Great work on the library, and I like the addition of the new extension methods :).
I noticed that the documentation for the Heap.Remove method claims an asymptotic upper bound of O(log n). However, the first line of the method is a call to Array.IndexOf, which I believe is O(n), which is faster growing than O(log n). I haven't analyzed the
method in detail, but removing that call should improve the efficiency of the method so that it actually is O(log n). I haven't looked at the efficiency of any other methodsthis just happened to catch my eye as I was perusing the source code :).
Cheers,
Mike


Coordinator
Feb 21, 2008 at 6:45 PM
Edited Feb 21, 2008 at 6:48 PM

Good catch. I actually added all that stuff the other day off the top of my head so bare with me on that as its sort of a skim at the moment.
Thanks for the catch.
p.s. if you find any others that are inaccurate please let me know, like I said it was skim through the source but I think the addition of this is pretty decent.
mstrobel wrote:
Hi there,
Great work on the library, and I like the addition of the new extension methods :).
I noticed that the documentation for the Heap.Remove method claims an asymptotic upper bound of O(log n). However, the first line of the method is a call to Array.IndexOf, which I believe is O(n), which is faster growing than O(log n). I haven't analyzed the
method in detail, but removing that call should improve the efficiency of the method so that it actually is O(log n). I haven't looked at the efficiency of any other methodsthis just happened to catch my eye as I was perusing the source code :).
Cheers,
Mike

