MagalooXX: Created page with " Just as a reminder as of how slowly the $log(log(n))$ function grows: {| class="wikitable" | $n$ | $log(log(n))$ |- |10 |0.83 |- |100 |1.53 |-..."

2014-10-07T09:52:26Z

Created page with " Just as a reminder as of how slowly the <math>log(log(n))</math> function grows: {| class="wikitable" |<math>n</math> |<math>log(log(n))</math> |- |10 |0.83 |- |100 |1.53 |-..."

New page

Just as a reminder as of how slowly the <math>log(log(n))</math> function grows:

{| class="wikitable"
|<math>n</math>
|<math>log(log(n))</math>
|-
|10
|0.83
|-
|100
|1.53
|-
|1000
|1.93
|-
|10000
|2.22
|}

The array will therefore consist of only very few distinct numbers and all others will be repetitions. An idea to sort such an array is the following

# First sweep through the original array and create two auxiliary arrays of numbers <math>A'=\{ a_1', a_2', a_3', \ldots \}</math> (with <math>\exists~ i,j: a_i=a_j</math>) and their repetition count <math>N=\{ n_1, n_2, n_3, \ldots \}</math> : this can be done in <math>O(n)</math> time
# Then sort the two arrays in parallel, comparing keys from <math>A'</math> : this can be done in <math>O(x\ log(x))</math> time with <math>x=log(log(n))</math>
# Finally recreate a sorted version of the original array by taking every number <math>a_i'</math> and repeat it <math>n_i</math> times : this can again be done in <math>O(n)</math> time

TADM2E 4.25 - Revision history

MagalooXX: Created page with " Just as a reminder as of how slowly the log(log(n)) function grows: {| class="wikitable" |n |log(log(n)) |- |10 |0.83 |- |100 |1.53 |-..."

MagalooXX: Created page with " Just as a reminder as of how slowly the $log(log(n))$ function grows: {| class="wikitable" | $n$ | $log(log(n))$ |- |10 |0.83 |- |100 |1.53 |-..."