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>
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)
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