Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The asymptotic lower bound for sorting n elements is n*log(n)

  1. Feb 9, 2009 #1
    the asymptotic lower bound for sorting n elements is n*log(n). what about sorting a set of n elements when you know that they only take on k distinct values? does n*log(k) sound right?
     
  2. jcsd
  3. Feb 9, 2009 #2
    Re: sorting

    Suppose that we could map each of the k values to the integers 1 to k. Also, suppose that we have k values in an array all set to 0. Then a sort would only look once at each number in a list. For each number the value is mapped to an index and the associated array element is incremented. Then the sort is completed by reporting as many values of each type as there are counts in each array element.

    cost of inspecting each value n
    + cost of mapping each value from 1 to k ??
    + cost of outputting the sorted list k
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: The asymptotic lower bound for sorting n elements is n*log(n)
  1. Number of digits in n! (Replies: 8)

  2. C++ power of n number (Replies: 13)

  3. N-body problem in Python (Replies: 10)

Loading...