Path: csiph.com!2.us.feeder.erje.net!feeder.erje.net!1.eu.feeder.erje.net!news2.arglkargh.de!news.mixmin.net!border2.nntp.ams1.giganews.com!nntp.giganews.com!buffer2.nntp.ams1.giganews.com!buffer1.nntp.ams1.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail NNTP-Posting-Date: Wed, 21 Dec 2016 13:28:54 -0600 From: Gareth Owen Newsgroups: comp.lang.c++ Subject: Re: Qucksort for Linked List References: <87d1gue00s.fsf@gmail.com> <42d98296-3339-4814-8ba9-d8d71607e5bc@googlegroups.com> <49d489dd-7c85-4bbf-a6a3-1d3e8034d6b0@googlegroups.com> Date: Wed, 21 Dec 2016 19:28:54 +0000 Message-ID: <87poklozd5.fsf@gmail.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux) Cancel-Lock: sha1:cR4/ymJt8Z8VnIU7vsWS+xPG314= MIME-Version: 1.0 Content-Type: text/plain Lines: 22 X-Usenet-Provider: http://www.giganews.com X-Trace: sv3-NNm23aGs0cA8qf2D52kiwtvWSiAWOtb9yXZK9NSZ3Wjtzf5OxxXOtmN9YJomiDN8CmiRCGRmazwVLOT!0UF25uzHIXS2EdZTPhEteu9/Wj4yDOs0o36afXxfFTN++yCbHULZHucpzI51iphvXfoh X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 2312 Xref: csiph.com comp.lang.c++:47484 leigh.v.johnston@googlemail.com writes: > Mr Flibble fully understands asymptotic complexity and Big-O notation. > > Mr Flibble claimed that the worst case complexity was more likely due > to poor pivot choice. > > Again Mr Flibble didn't claim the former was worse in asymptotic > complexity just that worst case complexity was more likely. "AFAIK quicksort will not work with linked lists;" "If by "works" you mean "works slowly, O(n)". "By "O(n)" I actually meant "worse than O(n)*O(lg N)". ******************************************************* ***** 'I actually meant "worse than O(n)*O(lg N)"' **** ******************************************************* I look forward to you Stuckling out of that. [Incidentally, you *actually* meant 'worse than O(N * lg N)']