Question

how many additional recursive partitioning levels are required for a list of 64 elements compared to a list of 8 elements?

Answer 1

If we have a list of 8 elements, we can partition it into halves by recursively splitting it 3 times:

8 -> 4 -> 2 -> 1

So for a list of 8 elements, we need 3 recursive partitioning levels.

For a list of 64 elements, we can partition it as:

64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1

So for a list of 64 elements, we need 6 recursive partitioning levels.

Therefore, for a list of 64 elements compared to a list of 8 elements, we require 3 additional recursive partitioning levels.

In general, if we have a list of N elements, the number of recursive partitioning levels required is log2(N). So going from 8 to 64 elements increases the levels by log2(64) - log2(8) = 6 - 3 = 3 additional levels.