thedominator's blog

What will be the time complexity of this operation?
By thedominator, history, 3 years ago, In English

i came across a string problem where i thought of an approach where the number of operations i am doing is equal to sum of all factors of n. Now i don't know if this will pass the time limit. Can anybody help? what will be the time complexity of such operation

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

What are the constraints? For a string of size $$$N$$$ up to $$$10^6$$$ would pass with an easy upperbound:

The approximate number of divisors of a number N is $$$\sqrt[3]{N}$$$. For $$$N=10^6$$$, the value would be up to $$$100$$$ divisors only. Approximately half of the divisors is smaller than $$$\sqrt{N}$$$ and half is bigger than $$$\sqrt{N}$$$. That means, an easy upperbound with no knowledge needed in maths is:

$$$\frac{\sqrt[3]{N}}{2} \cdot \sqrt{N} + \frac{\sqrt[3]{N}}{2} \cdot N$$$ upperbound.

Do not forget that in real case scenarios, it would be lower than that. Substituting in the above upperbound would yield around $$$5 \cdot 10^7$$$ which is pretty good.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks man!

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    I wrote a bit of C++ code to explicitly calculate it, and found that for $$$N \leq 10^6$$$, the maximum sum of divisors is $$$4\ 390\ 848$$$ (for $$$997\ 920$$$).

    And just for fun, I found that for $$$N \leq 10^8$$$, the max sum is $$$487\ 710\ 720$$$ (from $$$99\ 459\ 360$$$), and that the smallest $$$N$$$ with a sum exceeding $$$5 \times 10^7$$$ was $$$10\ 810\ 800$$$, which was referenced in the paper that Venti_chai linked.

    So I guess a good rule of thumb seems to be that the max sum of divisors of a number $$$\leq N$$$ is approximately $$$5N$$$ for your purposes.

    Code
    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This sequence is the numbers $$$a_1, a_2, \ldots$$$ where $$$a_k$$$ is the smallest positive integer such that its sum of factors is more than $$$k$$$ times itself. You can see that $$$a_6$$$ is about $$$10^8$$$, so for practitcal constraints ($$$\leq 10^6$$$ probably) the sum of divisors of $$$n$$$ will be less than $$$6n$$$.

→ Reply
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

If x*y=n, you can write x as n/y. Now for every x, y is unique and less than or equal to n. So a very loose upper bound of sum of all x is nlogn.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

In short, it's $$$O(n \log{\log{n}})$$$. Here's a sketch of a rough estimation:

The sum-of-divisors function $$$\sigma$$$ is a multiplicative function, so that for any positive integer $$$n$$$ with prime factorization $$$n = \prod_{i=1}^k p_i^{s_i}$$$, we have $$$\sigma(n) = \prod_{i=1}^k \sigma(p_i^{s_i}) = n \cdot \prod_{i=1}^k \frac{\sigma(p_i^{s_i})}{p_i^{s_i}}$$$. The sums-of-divisors for prime powers are easily calculated and seen to satisfy the inequality $$$\frac{p_i + 1}{p_i} \leq \frac{\sigma{p_i^{s_i}}}{p_i^{s_i}} \lt \frac{p_i}{p_i - 1}$$$. Taking logarithms and remembering a few things about convergent series from Calculus 2, we get that for some appropriate constant $$$C \in \mathbb{R}_{>0}$$$ which does not depend on $$$n$$$,

$$$\displaystyle \frac{n}{C} \exp \left(\sum_{i=1}^k \frac{1}{p_i} \right) \leq \sigma(n) \leq Cn \exp \left(\sum_{i=1}^k \frac{1}{p_i} \right).$$$

To get an upper bound, we can now make the rough estimation that the number $$$k$$$ of distinct prime factors of $$$n$$$ is at most $$$\log_2{n}$$$. This is a loose bound, but that's OK because it will be passed through a very slow-growing function: It in known that the sum of the reciprocals of the first $$$k$$$ primes is approximately $$$\ln (\ln{k}) + O(1)$$$. (For example, combine the Meissel-Mertens theorem with the prime number theorem. It's also clear that no set of $$$k$$$ distinct primes can do better.) So, we get that

$$$ \sigma(n) \leq Cn \exp ( \ln ( \ln ( \log_2{n} )) + O(1)) \leq D n \ln ( \ln{n}),$$$

for some appropriately chosen constant $$$D$$$ and all sufficiently large $$$n$$$, which is exactly the statement that $$$\sigma(n) \in O(n \log{\log{n}})$$$. To see that this bound isn't far from optimal (more precisely, to see $$$\sigma(n)$$$ is not in little-o $$$o(n \log{\log{n}})$$$), it suffices to consider values of $$$n$$$ that are large primorials and perform an identical computation with the left-hand side of the big inequality above.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

UPDATE: The solution got accepted for n= 2*(10^5) with time taken 207 ms. Thanks everyone. 120975508

→ Reply