How to analyse space complexity of algorithm for CountNonDivisible?

Question

I'm trying to analyse the worst-case space complexity of this algorithm for solving Codility's CountNonDivisible problem.

The problem statement:

You’re given an array A consisting of N integers.

For each number A[i] such that 0 ≤ i < N, we want to count the number of elements of the array that are not the divisors of A[i]. We say that these elements are non-divisors.

Write a function that, given such an array, returns a sequence of integers representing the amount of non-divisors for each element.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1, 50,000]

Each element of array A is an integer within the range [1, 2N].

The algorithm (with comments added by me):

def solution(A):
    A_max = max(A) # O(1) space
    count = {} # O(1) space

    # Create a count of the occurrences of each element in the input array.
    # O(N) space
    for element in A:
        if element not in count:
            count[element] = 1
        else:
            count[element] += 1

    divisors = {} # O(1) space

    # O(N) space
    for element in A:
        divisors[element] = set([1, element])

    divisor = 2 # O(1) space

    # Space TBC
    while divisor*divisor <= A_max:
        element_candidate = divisor # O(1) space
        while element_candidate <= A_max: # O(1) space
            if element_candidate in divisors and not divisor in divisors[element_candidate]: # O(1) space
                divisors[element_candidate].add(divisor) # O(1) space
                divisors[element_candidate].add(element_candidate//divisor) # O(1) space
            element_candidate += divisor # O(1) space
        divisor += 1 # O(1) space

    result = [0] * len(A) # O(N) space

    # Space TBC
    for idx, element in enumerate(A):
        result[idx] = (len(A) - sum([count.get(divisor,0) for divisor in divisors[element]]))

    return result

The article states that the expected worst-case space complexity is O(N).

But the divisors dict requires space for the sets of divisors it stores.

If each value in the dict were an integer, it would be clear to me why the worst-case space complexity is O(N). But each value is a set of integers.

So I think it follows that the total space required for the sets of divisors is proportional to the total number of divisors.

In the worst case, roughly how many divisors will be stored across all these sets?

The worst case should occur when, for a given N, we maximise the total number of divisors stored across all the sets.

To do this, I think we could use the following algorithm:

Construct an array, B, of size 2N, with elements equal to the first 2N values in the d(n) sequence - i.e., the sequence listing the number of divisors of n. (We take 2N values since the maximum value of any element in the input array to the CountNonDivisible problem is 2N.) Let B_i be the array of indices of B.
Sort the elements of B and B_i, first by the values in B (in descending order) and then by the values in B_i (also in descending order).
Then let worst-case input array A be the subarray consisting of the first N elements in B_i.

As an example, if N = 12, then 2N = 24 and, before sorting:

B_i = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]

B = [1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8]

And after sorting:

B_i = [24, 20, 18, 12, 16, 22, 21, 15, 14, 10, 8, 6, 9, 4, 23, 19, 17, 13, 11, 7, 5, 3, 2, 1]

B = [8, 6, 6, 6, 5, 4, 4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1]

And input array A = [24, 20, 18, 12, 16, 22, 21, 15, 14, 10, 8, 6]

The total number of divisors is 59.

What I’m struggling with is how to generalise this for any N in the range [1, 50,000].

I assume the O(N) worst-case space complexity is stated/proved somewhere by Codility, but I haven’t been able to find where.

Is my analysis above on the right lines? If so, how would I finish calculating the worst-case space complexity?

If not, then is it actually O(N)? And if it’s O(N), what am I doing wrong in my analysis?

user_5237560 · Answer

The solution is not really O(N) space because it is going to store a list of divisors for every element of A. Since the total number of divisors for numbers in the range 1..N increases with N, the complexity will be O(NxK) where K is the average number of divisors of 1..N over N.

If you print sum(map(len,divisors.values())) before returning the result, you'll find that solution([1,2,3,4,5,6,7,9,10]) has 27 entries in total of all the sets in the divisors dictionary (66 entries for 1..20, 111 for 1..30, 158 for 1..40, and so on with a ratio to N increasing from 2.7 to 3.95) This suggests a space complexity of O(Nxf(N)) where f(N) is some function that increases with N.

In short, the algorithm in the link does not meet the O(N) space expectation stated above. It does not meet the O(NlogN) time complexity expectation either.

If you were to use the sieve of Erathostenes (as suggested in the Codility execution statement), you would only need to store counters for N elements (or less) given that you only need to spread multiples of the distinct factors over multiples that actually exist in the list. This would meet the O(N) space requirement.

Here is a somewhat simpler implementation of the suggested logic:

def solution2(A):
    minA      = max(2,min(A)) # minimum multiple 
    maxA      = max(A)        # maximum multiple
    numCounts = dict.fromkeys(A,0)
    for n in A: numCounts[n] += 1 # distinct counts
    divCounts = numCounts.copy()  # divisor counts
    for n in numCounts:
        for m in range(minA*n,maxA+1,n):     # propagate multiples
            if m in divCounts:
                divCounts[m] += numCounts[m] # add factor count
    return [len(A)-divCounts[n] for n in A ]

numCounts / divCounts will contain at most N entries (ensuring O(N) space). Items in A that are > N will not iterate at all in the propagation loop so only items <= N will actually propagate their count to the multiples (in sieve fashion).

This however will have a time complexity greater than O(NlogN) because the number of propagations to multiples could be up to:

2N/2 + 2N/3 + 2N/4 ... + 2   # e.g. A = [2,3,4...,N,2N]

which is equivalent to

2N*∑(1/i) for [i=2..n]       # this is > N * log(N)

How to analyse space complexity of algorithm for CountNonDivisible?

1 Answers