Big-O notation

[Mike C. Fletcher]

Chad Netzer wrote:

>On Tue, 2003-04-15 at 13:32, Mike C. Fletcher wrote:
>  
>
>>Greg Brondo wrote:
>>    
>>
...

>>    * O(1) -- time is linear
>>    
>>
>
>You meant "time is constant".  The algorithm requires the same number of
>operations regardless of input size.
>  
>
Yup, absolutely correct, though in my defense, a horizontal line is 
linear too ;) . 

Don't post when tired (I just took a nap :) )!

>>    * O(N log N) -- see O(N) and O(log N), basically, you do an amount
>>      of work tied to the size of the whole set for every stage in an O(
>>      log N ) operation (this is comparatively rarely discussed in my
>>      experience).
>>    
>>
>
>Really?  Some of the most important classes of algorithms are O( N log N
>), specifically, many common sort algorithms.  
>
Ah, but I never took comp-sci, so I never got into those cool "what's 
the best sort algorithm" debates ;) .  Most of the debates I've gotten 
into this way have been around choices such as binary trees vs. hash 
tables, so that's probably skewed my experience.

...

>Also, one further class that is import to know is O( 2**N ), such as the
>brute-force solution to the "travelling salesman problem".  These are
>much, MUCH worse than O( N**2 ) algorithms, and even today can rarely be
>computed for problems sets much larger than 100 (whereas O( N**2 )
>problem sets can grow to thousands or perhaps even millions and still be
>practically solved).  Rather than computing "solutions" with these types
>of algorithms, it is required to instead come up with "close-enough" or
>"best guess" type algorithms that CAN be computed practically on large
>data sets.
>  
>
Cool.  Haven't come across an algorithm described as such, though I'd 
guess there've been a few that matched it over the years. 

Thanks for all the clarifications and corrections,
Mike

_______________________________________
  Mike C. Fletcher
  Designer, VR Plumber, Coder
  http://members.rogers.com/mcfletch/