Re: Inefficient algorithms

[Rick <rickduley@gmail.com>]

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.