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$>
References: <gnmlkm$n25$> <> <gnnudm$7aj$> <gnoa4p$j9q$> <gnq1pu$mtt$> <gnr4bb$ehi$>
Reply-To: <HIDDEN>
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: 1235324704 2959 (22 Feb 2009 17:45:04 GMT)
NNTP-Posting-Date: Sun, 22 Feb 2009 17:45:04 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: comp.soft-sys.matlab:520014

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gnr4bb$ehi$>...
> 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;

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