Re: Inefficient algorithms

[stefan-lucks@see-the.signature]

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