On Friday 02 May 2014 at 02:28:24, Daniel Horne wrote: > When you say > > > For lists: > > 1) Adding > > 2N > > > > 2) Merging > > constant > > > > 3) Sorting > > 2N*log(2N) > > > > Total: > > 2N+2N*log(2N) > > For the sorting pass, are you assuming use of quicksort? That would require > constant-time random access characteristics to achieve that efficiency (in > other words, transfer it to an array prior to sorting). Otherwise, you'd > have to add in a multiple of N for a linear scan on each item, making it > O(2N^2) by my reckoning. > > > (ps, apologies for possible duplicate post - hit reply to Ivan instead of > the list ) > > -- > DH I'm assuming usage of the in-kernel list_sort(), which uses merge sort and claims to have a complexity of O(n*log(n)). -- Ivan Shapovalov / intelfx /
Attachment:
signature.asc
Description: This is a digitally signed message part.
