There is some sorting, which in the process of operation dynamically receives blocks of memory of size sqrt (N), N is the number of elements of the array being sorted. ( This size IMHO has no relation to the essence of the question, but still ... )

Sort random data received by rand () (Linux, RAND_MAX = 2 ^ 31-1).

It is necessary to determine the dependence of K (the number of blocks) on N (the size of the array) .

I feel that it is kind of logarithmic (at least in a certain range (s) N), but it does not work out. For many data, a doubling of K with four times N is seen. How is it mathematically recorded?

NK 1000 3 2000 4 4000 5 8000 6 12000 7 16000 9 24000 10 32000 11 48000 12 50000 12 56000 13 64000 15 70000 15 75000 16 100000 16 150000 21 200000 24 280000 29 300000 31 400000 33 500000 37 600000 41 800000 48 1000000 54 1200000 57 1600000 68 2000000 78 2400000 81 3200000 95 4000000 105 6400000 131 12800000 189 16000000 211 64000000 420

If you have questions (including on unscheduled K, N), do not hesitate to ask, it’s not a problem to calculate. For large N (N> 10,000,000), do not worry.

I know about the forum for mathematicians, but I am afraid that we will speak different languages ​​there. Obviously things that are obvious to mathematicians will not be very clear to me.

    1 answer 1

    • After visualizing the dataset'a provided by you, you can immediately notice that the desired dependency is sublinear and then pick up the coefficients in the expression K = b * (N ^ a), 0 < a < 1

    • Specifically for your case, the function with parameters { a=0.492 , b=0.061 } , that is, will be a good approximation

    K = 0.061 * (N ^ 0.492)

    • Green on the graph shows the function proposed by me, blue - visualized source data set:

    alt text

    • And this is a practical proof of concept that the original dependency is not logarithmic)

    alt text

    • one
      Awesome It must be realized ... N ^ 0.492 is it almost sqrt (N)? Or I'm wrong ? To be honest, based on the algorithm, I thought it would be (log N, x) (this is if log their Emacs x - in emacs help is called base) (In general, I have already forgotten all such mathematics). So, I thought x would be about 1.5 or 1.25, since essentially 1/4 of the length of the merged array is sent to the queue ... @ Kotik_hochet_kushat, I, if frankly, did not enter the second schedule. Do you seem to some kind of "CAD" math. Do not look, here is such a "fractional" logarithm, does it fall ill? - avp
    • @avp - Yes, N ^ 0.492 is approximately N ^ (0.5) , i.e. sqrt . - It is difficult for me to make any assumptions about the algorithm, about which I do not know anything :) - The second graph suggests that the dependency function for the data you provided cannot be accurately expressed in the form a * ln(N) . - Costantino Rupert
    • @avp - Actually, it can be argued that in your case in the formula a * log N for any a there is a certain number N such that starting from this very number N graph a * log(N) will lie below the graph of the real dependence. That is, no matter how hard we try to pick up a dependency, representing it in the form of a * log(N) , we will fail. - Costantino Rupert
    • @ Kotik_khohet_kusat, thank you so much. How do you think this amount of memory should be described? There are blocks in sqrt (N). I wrote X * sqrt (N) where X = ??? . Now, instead of X, write 0.061 * (N ^ 0.492), or just 0.06 * N? The algorithm (and the program) the other day I plan to submit to the community. - avp pm
    • @avp - Theory of algorithms and [ Big O notation, ] [1] generally speaking, quite nontrivial things :) - First, some obtained data set cannot be a strict justification for saying: "Guys, this algorithm has a capacitive O(log N)" complexity O(log N)" - Secondly, 0.06 * sqrt(N) and 410241 * sqrt(N) are all O(sqrt(N)) [1]: en.wikipedia.org/wiki/Big_O_notation - Costantino Rupert