From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,9dfc10efb95ba130 X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,UTF8 Path: g2news1.google.com!news3.google.com!proxad.net!feeder1-2.proxad.net!usenet-fr.net!gegeweb.org!aioe.org!not-for-mail From: "John B. Matthews" Newsgroups: comp.lang.ada Subject: Re: Inefficient algorithms Date: Thu, 16 Sep 2010 16:19:19 -0400 Organization: The Wasteland Message-ID: References: <18f4ae08-3112-4f98-bb69-b76ebae6d2b2@p37g2000pra.googlegroups.com> <82880e4e-46a5-4c11-a6d4-a68cda551819@q26g2000vbn.googlegroups.com> NNTP-Posting-Host: LQJtZWzu+iKlBROuDg+IUg.user.speranza.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Complaints-To: abuse@aioe.org X-Notice: Filtered by postfilter v. 0.8.2 User-Agent: MT-NewsWatcher/3.5.3b3 (Intel Mac OS X) Xref: g2news1.google.com comp.lang.ada:14125 Date: 2010-09-16T16:19:19-04:00 List-Id: In article <82880e4e-46a5-4c11-a6d4-a68cda551819@q26g2000vbn.googlegroups.com>, "Chad R. Meiners" wrote: > On Sep 15, 5:45 pm, "John B. Matthews" wrote: > > In article > > <18f4ae08-3112-4f98-bb69-b76ebae6d...@p37g2000pra.googlegroups.com>, > > > >  Rick wrote: > > > Thanks BrianG but I was chasing O(2^n). > > > > The traditional recursive Fibonacci algorithm is exponential in n. > > > > > > And it is a nice example of an inefficient algorithm that can be made > efficient. Moreover, the computation can be made more efficient in several illustrative ways: 1. Iteration, having complexity O(n) and requiring memory O(1) 2. Closed form, having complexity O(1) and requiring memory O(1) 3. Memoization, having complexity O(n) and requiring memory O(n) -- John B. Matthews trashgod at gmail dot com