Inefficient algorithms

Inefficient algorithms

[Rick]

I am working on a class in algorithmic efficiency and, to make a
point, need an algorithm that runs O(2^n) - a factoring algorithm
perhaps.  All I can find is 'C' code I can't decipher.  Can someone
please help with an Ada example.

Thanks

Re: Inefficient algorithms

[J-P. Rosen]

Le 11/09/2010 06:24, Rick a �crit :
> I am working on a class in algorithmic efficiency and, to make a
> point, need an algorithm that runs O(2^n) - a factoring algorithm
> perhaps.  All I can find is 'C' code I can't decipher.  Can someone
> please help with an Ada example.
> 
Not exactly what you asked for, but a very inefficient array sorting
algorithm:
Generate all possible permutations, and then select the one that is sorted.
It's O(n!) both in time and space...

-- 
---------------------------------------------------------
           J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: Inefficient algorithms

[Robert A Duff]

"J-P. Rosen" <rosen@adalog.fr> writes:

> Not exactly what you asked for, but a very inefficient array sorting
> algorithm:
> Generate all possible permutations, and then select the one that is sorted.
> It's O(n!) both in time and space...

Here's an even slower method:  Generate all possible array
values, and select the one that is sorted and is a permutation
of the input.

;-)

- Bob

Re: Inefficient algorithms

[Niklas Holsti]

Rick wrote:
> I am working on a class in algorithmic efficiency and, to make a
> point, need an algorithm that runs O(2^n) - a factoring algorithm
> perhaps.  All I can find is 'C' code I can't decipher.  Can someone
> please help with an Ada example.

Perhaps the canonical example is this: you are given a Boolean formula 
containing n Boolean variables. Find a valuation (a value, True or 
False, for each variable) that makes the formula True. The O(2^n) 
algorithm tries each of the 2^n valuations in some order, evaluates the 
formula for this valuation, and stops when True.

In Ada, something like:

    N : constant := ...;

    type Valuation is array (1 .. N) of Boolean;
    -- Valuation(k) is the value of Boolean variable number k.

    function Formula (Inputs : Valuation) return Boolean
    is begin
       return <complex formula>;
    end Formula;

The search through all possible valuations is logically like an n-deep 
nested loop of the form

    for Value1 in Boolean loop
       for Value2 in Boolean loop
          ...
             for Value_n in Boolean loop
                if Formula ((Value1, Value2, ..., Value_n)) then
                   <exit and report success>.
                end if;
             end loop;
          ...
       end loop;
    end loop;

Since N is a variable, you cannot write out this N-deep loop nest in the 
Ada program. Instead, use a recursive function that is given a partial 
valuation, for example a valuation that gives the values for the 
variables 1 .. k, and then extends the valuation by trying both False 
and True values for variable k+1, calling itself recursively until it 
has a full valuation, when it calls Formula to see if this full 
valuation is a solution.

HTH,

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Inefficient algorithms

[Niklas Holsti]

Niklas Holsti wrote:
> Rick wrote:
>> I am working on a class in algorithmic efficiency and, to make a
>> point, need an algorithm that runs O(2^n) - a factoring algorithm
>> perhaps.  All I can find is 'C' code I can't decipher.  Can someone
>> please help with an Ada example.
> 
> Perhaps the canonical example is this: you are given a Boolean formula 
> containing n Boolean variables. Find a valuation (a value, True or 
> False, for each variable) that makes the formula True.

Replying to myself, since I realize that I probably misunderstood your 
need: what you want is an inefficient O(2^n) solution to an easy 
(non-exponential) problem. The problem I suggested is not, of course, an 
easy one. But it has easy variants. For example, require that the 
Boolean formula uses at most 10 of the n variables, where this limit 
(10) is considered a fixed number independent of the total number (n) of 
variables.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Inefficient algorithms

[Rick]

On Sep 11, 3:07 pm, Niklas Holsti <niklas.hol...@tidorum.invalid>
wrote:
> Niklas Holsti wrote:
> > Rick wrote:
> >> I am working on a class in algorithmic efficiency and, to make a
> >> point, need an algorithm that runs O(2^n) - a factoring algorithm
> >> perhaps.  All I can find is 'C' code I can't decipher.  Can someone
> >> please help with an Ada example.
>
> > Perhaps the canonical example is this: you are given a Boolean formula
> > containing n Boolean variables. Find a valuation (a value, True or
> > False, for each variable) that makes the formula True.
>
> Replying to myself, since I realize that I probably misunderstood your
> need: what you want is an inefficient O(2^n) solution to an easy
> (non-exponential) problem. The problem I suggested is not, of course, an
> easy one. But it has easy variants. For example, require that the
> Boolean formula uses at most 10 of the n variables, where this limit
> (10) is considered a fixed number independent of the total number (n) of
> variables.
>
> --
> Niklas Holsti
> Tidorum Ltd
> niklas holsti tidorum fi
>        .      @       .

I must be a bit daft, Niklas, but I don't get it.
What sort of a Boolean formula are you talking about?  How do I use it
in a recursive function?

You help is appreciated.
Thanks

Re: Inefficient algorithms

[Niklas Holsti]

Rick wrote:
> On Sep 11, 3:07 pm, Niklas Holsti <niklas.hol...@tidorum.invalid>
> wrote:
>> Niklas Holsti wrote:
>>> Rick wrote:
>>>> I am working on a class in algorithmic efficiency and, to make a
>>>> point, need an algorithm that runs O(2^n) - a factoring algorithm
>>>> perhaps.  All I can find is 'C' code I can't decipher.  Can someone
>>>> please help with an Ada example.
>>> Perhaps the canonical example is this: you are given a Boolean formula
>>> containing n Boolean variables. Find a valuation (a value, True or
>>> False, for each variable) that makes the formula True.
>> Replying to myself, since I realize that I probably misunderstood your
>> need: what you want is an inefficient O(2^n) solution to an easy
>> (non-exponential) problem. The problem I suggested is not, of course, an
>> easy one. But it has easy variants. For example, require that the
>> Boolean formula uses at most 10 of the n variables, where this limit
>> (10) is considered a fixed number independent of the total number (n) of
>> variables.
>>
>> --
>> Niklas Holsti
>> Tidorum Ltd
>> niklas holsti tidorum fi
>>        .      @       .
> 
> I must be a bit daft, Niklas, but I don't get it.
> What sort of a Boolean formula are you talking about?

For example, in Ada, with N = 4:

    type Bool_Valuation is array (1 .. 4) of Boolean;

    function Formula (Input : Bool_Valuation) return Boolean
    is
    begin

       return Input(1)
          and Input(2) /= Input (4)
          and (Input(3) or (Input(1) and Input(4)))
          and (Input(2) /= Input(1));

    end Formula;

The problem is to find some value of the Input parameter (that is, 4 
Boolean values, one each for Input(1), Input(2), Input(3), and Input(4)) 
such that Formula (Input) returns True. One solution is (True, False, 
False, True).

In real applications of the Boolean satisfiability problem, the number 
of variables can be huge (thousands or millions, I believe -- it keeps 
increasing year by year). In real applications the Formula would 
typically not be written out in Ada, as in the above example, but would 
be given as input to the program and represented by some data structure.

The brute-force exponential algorithm is to try all possible values of 
the Input parameter. There are 2**4 = 16 such values in the example.

> How do I use it in a recursive function?

The recursion is just used to enumerate (go through) all possible values 
of the Input parameter when (as in the general case) the length of the 
Input vector is some variable N. The idea is to first enumerate all 
values of Input where Input(1) = False, and then (if no solution was 
found yet) enumerate all values of Input where Input(1) = True. To 
enumerate all Inputs where Input(1) has a given value, a recursive call 
is used to enumerate all the values of the rest of the Input, which is 
Input(2..N). The recursion ends when it is trying a value for Input(N), 
and then it just calls Formula (Input); if the result is True, this 
value of Input is a solution.

I have placed example Ada code at http://www.tidorum.fi/soldem.zip.

But I repeat, this problem is a hard one, for which it is not easy to 
find more efficient general solutions, unless you know something more 
about the formula. For example, if you know that it uses at most 10 
variables (not all the N variables), you can inspect the formula to find 
which 10 variables it uses and then limit the search to all the possible 
values of these 10 variables, giving a constant 2**10 number of choices 
instead of the general 2**N.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Inefficient algorithms

[Rick]

Thanks Niklas Holsti.
Thank you especially for taking the time to provide me with example
code.
You have been very helpful.

Re: Inefficient algorithms

[Ludovic Brenta]

Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
> Niklas Holsti wrote:
>> Rick wrote:
>>> I am working on a class in algorithmic efficiency and, to make a
>>> point, need an algorithm that runs O(2^n) - a factoring algorithm
>>> perhaps.  All I can find is 'C' code I can't decipher.  Can someone
>>> please help with an Ada example.
>>
>> Perhaps the canonical example is this: you are given a Boolean
>> formula containing n Boolean variables. Find a valuation (a value,
>> True or False, for each variable) that makes the formula True.
>
> Replying to myself, since I realize that I probably misunderstood your
> need: what you want is an inefficient O(2^n) solution to an easy
> (non-exponential) problem. The problem I suggested is not, of course,
> an easy one. But it has easy variants. For example, require that the
> Boolean formula uses at most 10 of the n variables, where this limit
> (10) is considered a fixed number independent of the total number (n)
> of variables.

Actually I do think that the problem is trivial and that you can solve
it without recursion.  If you see your array of Booleans as a number in
binary representation:

procedure Inefficient (N : in Natural) is

   subtype Valuation is Natural range 1 .. 2**N;

   -- We assume the solution is Valuation'Last but it could be any value.
   Solution : constant Valuation := Valuation'Last;
begin
   for K in Valuation'Range loop
      exit when K = Solution;
   end loop;
end Inefficient;

-- 
Ludovic Brenta.

Re: Inefficient algorithms

[Ludovic Brenta]

I just wrote on comp.lang.ada:
> Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
>> Niklas Holsti wrote:
>>> Rick wrote:
>>>> I am working on a class in algorithmic efficiency and, to make a
>>>> point, need an algorithm that runs O(2^n) - a factoring algorithm
>>>> perhaps.  All I can find is 'C' code I can't decipher.  Can someone
>>>> please help with an Ada example.
>>>
>>> Perhaps the canonical example is this: you are given a Boolean
>>> formula containing n Boolean variables. Find a valuation (a value,
>>> True or False, for each variable) that makes the formula True.
>>
>> Replying to myself, since I realize that I probably misunderstood your
>> need: what you want is an inefficient O(2^n) solution to an easy
>> (non-exponential) problem. The problem I suggested is not, of course,
>> an easy one. But it has easy variants. For example, require that the
>> Boolean formula uses at most 10 of the n variables, where this limit
>> (10) is considered a fixed number independent of the total number (n)
>> of variables.
>
> Actually I do think that the problem is trivial and that you can solve
> it without recursion.  If you see your array of Booleans as a number in
> binary representation:
>
> procedure Inefficient (N : in Natural) is
>
>    subtype Valuation is Natural range 1 .. 2**N;

Make that 0 .. 2**N, of course.

>    -- We assume the solution is Valuation'Last but it could be any value.
>    Solution : constant Valuation := Valuation'Last;
> begin
>    for K in Valuation'Range loop
>       exit when K = Solution;
>    end loop;
> end Inefficient;

Granted, a decent optimizing compiler might grab victory from the jaws
of defeat in this case :)

-- 
Ludovic Brenta.

Re: Inefficient algorithms

[Niklas Holsti]

Ludovic Brenta wrote:
> Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
>> Niklas Holsti wrote:
>>> Rick wrote:
>>>> I am working on a class in algorithmic efficiency and, to make a
>>>> point, need an algorithm that runs O(2^n) - a factoring algorithm
>>>> perhaps.  All I can find is 'C' code I can't decipher.  Can someone
>>>> please help with an Ada example.
>>> Perhaps the canonical example is this: you are given a Boolean
>>> formula containing n Boolean variables. Find a valuation (a value,
>>> True or False, for each variable) that makes the formula True.
>> Replying to myself, since I realize that I probably misunderstood your
>> need: what you want is an inefficient O(2^n) solution to an easy
>> (non-exponential) problem. The problem I suggested is not, of course,
>> an easy one. But it has easy variants. For example, require that the
>> Boolean formula uses at most 10 of the n variables, where this limit
>> (10) is considered a fixed number independent of the total number (n)
>> of variables.
> 
> Actually I do think that the problem is trivial and that you can solve
> it without recursion.  If you see your array of Booleans as a number in
> binary representation:
> 
> procedure Inefficient (N : in Natural) is
> 
>    subtype Valuation is Natural range 1 .. 2**N;

That will of course fail to compile when N grows large enough, as it 
will when we are talking of order-of-complexity questions. (Also, I 
think you really wanted the range 0 .. 2**N - 1, giving the N-bit binary 
numbers).

>    -- We assume the solution is Valuation'Last but it could be any value.
>    Solution : constant Valuation := Valuation'Last;
> begin
>    for K in Valuation'Range loop
>       exit when K = Solution;

Here you are assuming that the Boolean formula has the simple form

    Var1 = K1 and Var2 = K2 and Var3 = K3 and ... Var<N> = K<N>

where K1..K<N> are the Boolean constants that correspond to the constant 
bits in your Solution. I had in mind a more general formula where, for 
example, we can compare two variables (Var1 = Var4), negate variables, 
and so on.

In the terms of my first post, this algorithm would be:

    -- The formula for which a solution is sought:

    function Formula (Input : Valuation) return Boolean
    is begin
       return <a complex Boolean formula depending on the N bits
               in the Input parameter>;
    end Formula;

    -- The search for the solution:

    for K in Valuation loop
       exit when Formula (K);
    end loop;

A trivial amount of code, indeed, but since Valuation has 2**N values, 
the loop will iterate 2**N times, so this algorithm is also O(2**N), as 
for the recursive one.

This example is just the Boolean satisfiability problem (SAT), a 
well-known difficult problem, which is not trivial in the general case.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Inefficient algorithms

[Peter C. Chapin]

On 2010-09-11 07:20, Niklas Holsti wrote:

> This example is just the Boolean satisfiability problem (SAT), a
> well-known difficult problem, which is not trivial in the general case.

Indeed, SAT is NP-complete. I believe it may have been the first problem
proved to be NP-complete (not sure). So if P /= NP as many people
suspect, there is no polynomial time way of solving SAT.

Peter

Re: Inefficient algorithms

[stefan-lucks]

On Fri, 10 Sep 2010, Rick wrote:

> I am working on a class in algorithmic efficiency and, to make a
> point, need an algorithm that runs O(2^n) - a factoring algorithm
> perhaps.  All I can find is 'C' code I can't decipher.  Can someone
> please help with an Ada example.

Technically,all polynomial-time algorithms are in O(2^n), since the 
"big-Oh" means something like "not faster than". 

But if you really need (worst-case) exponential time, here is such an 
algorithm for for factoring a number n (or for detecting if n is prime):

function Factor(C: Positive) return (Positive or "is prime") is
  -- pre C>1
begin
  for I in 2 .. C-1 loop 
    if I divides C then 
      return I
    end if
  end loop
  return "is prime"
end Factor;

This is pseudo-code with an Ada-like syntax, and shouldn't be hard to 
translate into Ada. (Hey, this is *your* homework!)

Note that if C is a prime, this the loop iterates C-2=Theta(C) times. If C 
is an n-bit prime, the number of iterations is 
   2**(log_2(C)) - 2  >  2**(n-1) - 2.

-- 
------ Stefan Lucks   --  Bauhaus-University Weimar  --   Germany  ------
               Stefan dot Lucks at uni minus weimar dot de
------  I  love  the  taste  of  Cryptanalysis  in  the  morning!  ------

Re: Inefficient algorithms

[Wilson]

I'm not sure if this is what you are looking for or not.  How about  
printing out all permutations of the first n integers?  The algorithm is  
in many texts along with an explanation.  See, for example:
http://en.wikipedia.org/wiki/Permutation


I'm also don't know which 2**n algorithm is simplest to write or  
understand, but there are literally thousands of problems that meet this  
criteria.  By the way, none of these problems are strictly speaking  
"inefficient".  Instead, they are just "computationally tedious"(My  
term)!  (I am taking inefficient to mean that a faster algorithm exits.)

In many of these problems (such as printing all the permutations) a faster  
algorithm is impossible. On the other hand, NP-Complete problems such as  
the binary problem discussed in some of the other posts have no known  
faster solution; i.e., a faster solution might exist, but we have no proof.

Good luck which ever way you choose to go.



--- news://freenews.netfront.net/ - complaints: news@netfront.net ---

Re: Inefficient algorithms

[Rick]

Hi Stefan

I have a couple of problems with this algorithm:

> But if you really need (worst-case) exponential time, here is such an
> algorithm for for factoring a number n (or for detecting if n is prime):
>
> function Factor(C: Positive) return (Positive or "is prime") is
>   -- pre C>1
> begin
>   for I in 2 .. C-1 loop
>     if I divides C then
>       return I
>     end if
>   end loop
>   return "is prime"
> end Factor;

1.  This algorithm depends on a single loop.  As I understand loops,
the worst case scenario is C-2 iterations.  That is to say the
algorithm is linear i.e. O(n).

2. How can I write a function which returns a 'choice' of type?  All I
can think of is some trick with discriminate record.

Re: Inefficient algorithms

[Georg Bauhaus]

On 9/12/10 3:53 AM, Rick wrote:
> Hi Stefan
>
> I have a couple of problems with this algorithm:
>
>> But if you really need (worst-case) exponential time, here is such an
>> algorithm for for factoring a number n (or for detecting if n is prime):
>>
>> function Factor(C: Positive) return (Positive or "is prime") is
>>    -- pre C>1
>> begin
>>    for I in 2 .. C-1 loop
>>      if I divides C then
>>        return I
>>      end if
>>    end loop
>>    return "is prime"
>> end Factor;
>
> 1.  This algorithm depends on a single loop.

I think the above function wasn't meant to be the completed solution
of "find all (prime) factors of a number".  Also, I'd count the
steps it takes the computer to perform the operations inside
the loop.


> 2. How can I write a function which returns a 'choice' of type?  All I
> can think of is some trick with discriminate record.

Doesn't have to be a choice of types, just choice might be enough.

       type Positive_Or_Is_Prime is private;

       subtype Greater_Than_1 is Positive range 1+1 .. Positive'Last;

       function To_Positive_Or_Is_Prime
	(P : Positive) return Positive_Or_Is_Prime;
       function To_Greater_Than_1
         (X : Positive_Or_Is_Prime) return Greater_Than_1;
       function Is_Prime (X : Positive_Or_Is_Prime) return Boolean;

    private
       type Positive_Or_Is_Prime is range 1 .. Positive'Last;
       Is_Prime_Number : constant Positive_Or_Is_Prime := 1;

Re: Inefficient algorithms

[stefan-lucks]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2025 bytes --]

On Sat, 11 Sep 2010, Rick wrote:

> Hi Stefan
> 
> I have a couple of problems with this algorithm:
> 
> > But if you really need (worst-case) exponential time, here is such an
> > algorithm for for factoring a number n (or for detecting if n is prime):
> >
> > function Factor(C: Positive) return (Positive or "is prime") is
> > � -- pre C>1
> > begin
> > � for I in 2 .. C-1 loop
> > � � if I divides C then
> > � � � return I
> > � � end if
> > � end loop
> > � return "is prime"
> > end Factor;
> 
> 1.  This algorithm depends on a single loop.  As I understand loops,
> the worst case scenario is C-2 iterations.  That is to say the
> algorithm is linear i.e. O(n).

No, n is the number of bits required to store C. So the algorithm is 
exponential in the input size, which is what one usually counts. 

> 2. How can I write a function which returns a 'choice' of type?  All I
> can think of is some trick with discriminate record.

Think of an underlying application. One application might be a test if C 
is prime. You need a function Is_Prime(C: Positive) return Boolean. 
Replace "return I" by "return False". Another application may actually as 
for the smallest positive factor of C (except for 1). In that case, you 
could "return C" instead of "return 'is prime'". 

Instead of returning something, one may also call a subprogram:

type Callback_1 is access procedure (Candidate: Positive);
type Callback_2 is access procedure (Candidate, Factor: Positive);

procedure Factor(C: Positive; 
                 Found_A_Factor: Callback_2;
                 Is_Prime: Callback_1) is 
   -- pre C>1
begin
  for I in 2 .. C-1 loop
    if I divides C then
      Found_A_Factor(Candidate => C, Factor => I);
      return;
    end if;
  end loop;
  Is_Prime(C);
  return; 
end Factor;






-- 
------ Stefan Lucks   --  Bauhaus-University Weimar  --   Germany  ------
               Stefan dot Lucks at uni minus weimar dot de
------  I  love  the  taste  of  Cryptanalysis  in  the  morning!  ------

Re: Inefficient algorithms

[BrianG]

Rick wrote:
> I am working on a class in algorithmic efficiency and, to make a
> point, need an algorithm that runs O(2^n) - a factoring algorithm
> perhaps.  All I can find is 'C' code I can't decipher.  Can someone
> please help with an Ada example.
> 
> Thanks
Um, after reading all the responses to date, I don't uderstand what's so 
hard about coming up with an _IN_efficient example.  I'd think any first 
year programming class ought to provide at least one good example.

How about:

------------------------------------------------------------------------------- 

-- Bad_Sort.Ada - Example of O(n^2) code
------------------------------------------------------------------------------- 

    with Ada.Text_IO, Ada.Integer_Text_IO;
    use  Ada.Text_IO, Ada.Integer_Text_IO;
procedure Bad_Sort is
    type My_Array is array (Natural range <>) of Integer;
    function Sort (This : My_Array) return My_Array is
       Input  : My_Array := This;
       Result : My_Array (This'first..This'last);
       Min, Index : Integer;
    begin
       for I in Result'range loop
          Min := Integer'last;
          Index := Input'first-1;
          for J in Input'range loop
             if Input(J) < Min then
                Min := Input(J);
                Index := J;
             end if;
          end loop;
          Result(I) := Min;
          if Index >= Input'first then
             Input(Index) := Integer'last;
          end if;
       end loop;
       return Result;
    end Sort;
    --
    Test : My_Array := (1, 3, 2, 5, 7, 4, 9, 8, 6, 0);
    Answ : My_Array := Sort(Test);
begin
    Put("Input: ");
    for I in Test'range loop
       Put(Test(I));
    end loop;
    New_Line;
    Put("Output:");
    for I in Answ'range loop
       Put(Answ(I));
    end loop;
    New_Line;
end Bad_Sort;

(of course, this is an O(n^2) implementation; maybe that's not what you 
meant :-)

Re: Inefficient algorithms

[Rick]

Thanks BrianG but I was chasing O(2^n).

Re: Inefficient algorithms

[John B. Matthews]

In article 
<18f4ae08-3112-4f98-bb69-b76ebae6d2b2@p37g2000pra.googlegroups.com>,
 Rick <rickduley@gmail.com> wrote:

> Thanks BrianG but I was chasing O(2^n).

The traditional recursive Fibonacci algorithm is exponential in n.

<http://courses.csail.mit.edu/6.01/spring07/lectures/lecture4.pdf>

-- 
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>

Re: Inefficient algorithms

[Chad R. Meiners]

On Sep 15, 5:45 pm, "John B. Matthews" <nos...@nospam.invalid> wrote:
> In article
> <18f4ae08-3112-4f98-bb69-b76ebae6d...@p37g2000pra.googlegroups.com>,
>
>  Rick <rickdu...@gmail.com> wrote:
> > Thanks BrianG but I was chasing O(2^n).
>
> The traditional recursive Fibonacci algorithm is exponential in n.
>
> <http://courses.csail.mit.edu/6.01/spring07/lectures/lecture4.pdf>
>
> --
> John B. Matthews
> trashgod at gmail dot com
> <http://sites.google.com/site/drjohnbmatthews>

And it is a nice example of an inefficient algorithm that can be made
efficient.

Re: Inefficient algorithms

[John B. Matthews]

In article 
<82880e4e-46a5-4c11-a6d4-a68cda551819@q26g2000vbn.googlegroups.com>,
 "Chad  R. Meiners" <chad.rmeiners@gmail.com> wrote:

> On Sep 15, 5:45 pm, "John B. Matthews" <nos...@nospam.invalid> wrote:
> > In article
> > <18f4ae08-3112-4f98-bb69-b76ebae6d...@p37g2000pra.googlegroups.com>,
> >
> >  Rick <rickdu...@gmail.com> wrote:
> > > Thanks BrianG but I was chasing O(2^n).
> >
> > The traditional recursive Fibonacci algorithm is exponential in n.
> >
> > <http://courses.csail.mit.edu/6.01/spring07/lectures/lecture4.pdf>
> 
> 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)

<http://en.wikipedia.org/wiki/Fibonacci_number>

3. Memoization, having complexity O(n) and requiring memory O(n)

<http://www.itl.nist.gov/div897/sqg/dads/HTML/memoize.html>

-- 
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>

Re: Inefficient algorithms

[Rick]

Thank you John B Matthews.
That set of lecture notes was very useful.