Re: sqrt (was Re: A89: TI-GCC)
[Prev][Next][Index][Thread]
Re: sqrt (was Re: A89: TI-GCC)
O(n) is known as Big O notation. The basic concept is how many loops it has
to make based on n-the number of items in the array or whatever. For
instance, a good ol' selection sort algorithm takes O(n^2) because it goes
through the array and inside that goes through the array again. Good sort
algorithms like quicksort take O(n log n) which is, needless to say, a whole
lot faster. O(n) means you go through the array only one time. O(1) is
equivalent to accessing an array based on an index (ie it only takes one
"cycle" no matter how large the array is. The smaller Big O an algorithm
has, the faster.
In a message dated 3/28/00 8:20:51 PM Eastern Standard Time,
noveck@pluto.njcc.com writes:
> Once again, my algorithm is shot down. But constructive criticism is always
> welcome. . . more below:
>
> > The algorithm works, but it's slower. A rough time complexity analysis
> > reveals that your algorithm is O(sqrt(n)), while the other algorithm is
> > O(log n) (or O(1) if you prefer).
>
> How is this determined? What exactly is that notation?
>
> > the algorithm below (modified
> > to the new integer size of course) returned the answer "instantly", while
> > your algorithm (also modified of course) never returned an answer at
> all...
> > (It would, eventually, but I didn't want to spend the whole night waiting
> > for it... :) )
>
> LOL - figures. Wouldn't think it would be THAT long, though. . .
>
> Could you elaborate on how that O(log n) algorithm works? I don't quite
> understand it, and working through it is "confusing" at the least.
>
----
Jonah Cohen
<ComAsYuAre@aol.com>
http://members.xoom.com/JonahCohen/