Path: news.mathworks.com!not-for-mail From: <HIDDEN> Newsgroups: comp.soft-sys.matlab Subject: Re: Go from end to start of array Date: Sun, 22 Feb 2009 17:45:04 +0000 (UTC) Organization: The MathWorks, Inc. Lines: 16 Message-ID: <gns2v0$2sf$1@fred.mathworks.com> References: <gnmlkm$n25$1@fred.mathworks.com> <28689491.1235151366987.JavaMail.jakarta@nitrogen.mathforum.org> <gnnudm$7aj$1@fred.mathworks.com> <gnoa4p$j9q$1@fred.mathworks.com> <gnq1pu$mtt$1@fred.mathworks.com> <gnr4bb$ehi$1@fred.mathworks.com> Reply-To: <HIDDEN> NNTP-Posting-Host: webapp-05-blr.mathworks.com Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 8bit X-Trace: fred.mathworks.com 1235324704 2959 172.30.248.35 (22 Feb 2009 17:45:04 GMT) X-Complaints-To: news@mathworks.com NNTP-Posting-Date: Sun, 22 Feb 2009 17:45:04 +0000 (UTC) X-Newsreader: MATLAB Central Newsreader 1187260 Xref: news.mathworks.com comp.soft-sys.matlab:520014 "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gnr4bb$ehi$1@fred.mathworks.com>... > The naive algorithm is not fast at all. Deleting single element on a loop brings the complexity to O(n^2) on the memory access count. It is obviously slow for large n, regardless m. > > Bruno It would only be order n^2 if you were calculating the final a's for each value from 1 to n, performing each deletion task separately. However that task is most efficiently carried out by m = 5; % Or whatever m you choose a = ones(1,N); for n = 1:N-1 a(n+1) = mod(a(n)+m-2,n)+2; end which would accomplish the same thing in order n. Note that this isn't tracing out the successive deletions. It is solving each a-problem in one step, but it has to start with n = 1 to do so. I would judge that this is the best algorithm one could use to generate an entire list of the final a's from 1 to some N. (That is, unless someone comes up with some kind of formula for the a's that can be vectorized.) Roger Stafford