Path: csiph.com!feeder.erje.net!2.eu.feeder.erje.net!border1.nntp.ams1.giganews.com!nntp.giganews.com!buffer1.nntp.ams1.giganews.com!buffer2.nntp.ams1.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 23 Dec 2016 14:56:30 -0600
From: Gareth Owen <gwowen@gmail.com>
Newsgroups: comp.lang.c++
Subject: Re: Qucksort for Linked List
References: <dfa00771-7568-443b-ab45-174f0749a176@googlegroups.com> <o2m7v7$2s1e$1@adenine.netfront.net> <a8ydnTLbnp2tcNPFnZ2dnUU7-bGdnZ2d@neganews.com> <o2o7q6$2prn$1@adenine.netfront.net> <yuudnRfdreaAqM3FnZ2dnUU7-LudnZ2d@giganews.com> <o2rcld$nhd$1@dont-email.me> <87d1gue00s.fsf@gmail.com> <mrSdnUOdRsH4JczFnZ2dnUU7-TGdnZ2d@giganews.com> <o30hk4$112$1@adenine.netfront.net> <ANqdnaKugKq-78nFnZ2dnUU7-VWdnZ2d@giganews.com> <kfnpokrdor0.fsf@x-alumni2.alumni.caltech.edu> <o384ef$1irf$1@adenine.netfront.net> <kfnh95vdvmc.fsf@x-alumni2.alumni.caltech.edu> <rJGdncoOaMmTxcDFnZ2dnUU7-emdnZ2d@giganews.com> <kfnbmw2za3d.fsf@x-alumni2.alumni.caltech.edu> <qqGdnYbwue6uFcDFnZ2dnUU7-budnZ2d@giganews.com>
Date: Fri, 23 Dec 2016 20:56:30 +0000
Message-ID: <87a8bm4b5t.fsf@gmail.com>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux)
Cancel-Lock: sha1:SVccKY3C7g5WSaBqXb0Qwbu7wZ0=
MIME-Version: 1.0
Content-Type: text/plain
Lines: 17
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-Du636SovB0pEgzfrIqvQzwNPVyuvz9S6h6Xj/OFKrEs89AjH6kNzlooWflAY704cfpGnV4Wdk4iHuJQ!7uxbbKX8cSfiYlgddd5GowKAv6RmU0StXmbCmnhV8CTWeJDI0Mx0j41GP8cYdOH7amqw
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: 2212
Xref: csiph.com comp.lang.c++:47562

Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes:

> So how to get the middle element without traversing linked list O(n)
> times for each partition?

If each interation used to take k*n steps (fixed k) now takes (k+1)*n steps,
             **** YOU HAVEN'T CHANGED THE ORDER ****

If each interation used to take k*n steps and now takes 1000*k*n steps,
you've slowed the algorithm down egregiously but....
            **** YOU STILL HAVEN'T CHANGED THE ORDER ****

Maths not a strong suit, is it?

> You are basically contradicting yourself.

You are wrong.  Go read a book.