What is the running Time complexity of this algorithm that getting all submultiples of n?

user_9238733 0
Viewed 64
def get_submultiples(n):
    # Get all submultiples of n
    if n == 1:
        return [1]
    i = 2
    submultiples = set([1,n])
    m = n
    while i < m:
        if n % i != 0:
            m = int(n/i)+1
        else:
            submultiples.add(i)
            submultiples.add(int(n/i))
        i += 1
    return submultiples
  1. this algorithm wrote by myself, I want to know what is its O(?). Can anybody help me?
  2. it wrote by python and "n" is an integer.
algorithm python
1 Answers

The Big-O complexity is complicated by the fact that you conditionally shrink m. The more factors n has, the less often you shrink m. If it has few factors the complexity approaches O(√n), but if it has many the complexity is closer to O(n). I don't know exactly how that shakes out for arbitrary values of n.

You could improve this by shrinking m every iteration, regardless of whether i is a factor or not. This would then be equivalent to simply having a fixed upper limit of √n, which would give a predictable runtime of O(√n).

def get_submultiples(n):
    submultiples = set()
    for i in range(1, math.ceil(math.sqrt(n)) + 1):
        if n % i == 0:
            submultiples.add(i)
            submultiples.add(n // i)
    return submultiples

You could also write it using a generator expression:

def get_submultiples(n):
    return set(itertools.chain.from_iterable(
        (i, n // i)
        for i in range(1, math.ceil(math.sqrt(n)) + 1)
            if n % i == 0
    ))

Or as a generator:

def get_submultiples(n):
    for i in range(1, math.ceil(math.sqrt(n)) + 1):
        if n % i == 0:
            yield i
            yield n // i
user_685870
Related