Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Pentatonic mode and a solution to the order of the primes...

Expand Messages
  • Décio Luiz Gazzoni Filho
    Oh, and WTF does the pentatonic have to do with primes? Unless you re going to compose a song called `The Prime Blues or something. Décio [Non-text portions
    Message 1 of 5 , Feb 11, 2005
    • 0 Attachment
      Oh, and WTF does the pentatonic have to do with primes? Unless you're going to
      compose a song called `The Prime Blues' or something.

      Décio


      [Non-text portions of this message have been removed]
    • Jens Kruse Andersen
      ... Sorting is provably O(n log n) and no better _if_ it is only based on comparing 2 elements at a time, e.g. with
      Message 2 of 5 , Feb 11, 2005
      • 0 Attachment
        > BTW, is it really linear? I've always thought sorting was O(n log n),
        > although some people described supposedly O(n) sorts but there
        > always seemed to be some sort of catch.

        Sorting is provably O(n log n) and no better _if_ it is only based on
        comparing 2 elements at a time, e.g. with <.

        If something useful is known about the elements, e.g. so they can easily be
        divided into certain subsets, then sorting often becomes O(n).

        Sorting integers is linear if the bits (or digits) can be extracted in linear
        time.
        With bits, the numbers can be placed in a binary tree with 0=left and 1=right
        in linear time. The sorted numbers can then be read in linear time by
        traversing the tree.

        Alphabetic sorting is linear if the letters can be extracted. E.g. place words
        in a tree with 26 children for each node.

        Sorting floats is linear e.g. if the binary representation can be recovered
        and understood. Then the mantissa and exponent can be sorted separately.

        In practice on typical sizes, linear sorting algorithms may often turn out
        slower or require more space than practical.

        --
        Jens Kruse Andersen
      Your message has been successfully submitted and would be delivered to recipients shortly.