# Tight bound on the number of divisors of n

The inner loop of this pseudocode runs only for the divisors of n

for i=1 to n:
if(n%i==0):
for j=1 to n:
Do something in constant time


If I can get a bound on the number of divisor of n(The condition in the if statement) then I can get its time complexity.Please Help ?

• What is your question? Do you want to find the complexity of your C code? What is input? – fade2black Aug 20 '17 at 22:12
• Yes I want to find the time complexity of this code ! – Pradeep Kumar Aug 20 '17 at 22:13
• We are happy to help you, but programming questions is off-topic here. You should first clearly state what you want to solve, then provide a pseudocode with input, then what you think and have done, and your question. By the way, why do you loop $n$ times if $n$ is divisible by $i$? – fade2black Aug 20 '17 at 22:18
• The number of divisors can be anything from 2 to roughly $n^{1/\log\log n}$, and is on average $\log n$ (in a certain precise sense). See the Wikipedia article for more details. – Yuval Filmus Aug 20 '17 at 22:23
• I'm voting to close this question as off-topic because the actual question is "Please give me tight bounds on the number of divisors of a given natural number", which is a question of pure mathematics, not computer science. – David Richerby Aug 16 '18 at 14:23

Your test whether i is a divisor of n runs for all 1 ≤ i ≤ n, therefore the execution time is at least $\theta(n)$. You can easily reduce that to $\theta(n^{1/2})$ be finding divisors $i≤n^{1/2}$ and observing that with a divisor i, n / i is also a divisor.

• If $i$ is a divisor, the nested loop costs $\Theta(n)$, so the complexity would be $\Theta(n\cdot(\text{the number of divisors of$n$}))$. – xskxzr Apr 14 at 11:14

Assume your input is $n$. I also assume that you know that we measure the time complexity of an algorithm as a function of input length to this algorithm which is $\log_2{n}$ in this case. Then even the following simple loop would take exponential time (as a function of input size)

for i=1 to n:
print "hi"
end


since it loops $n$ times, where $n = 2^{\log_2{n}} = 2^{\text{input size}}$.

More precisely, its running time (as Yuval Filmus commented) is roughly $O(nn^{1/{\log{\log{n}}}})$ which is still exponential. But since your algorithm is $O(n^2)$ it is pseudo polynomial (polynomial in the numeric value of the input, not input size).

• The inner loop only works for the divisors of n so the running time of this code would be (number of divisors of n multiplied by n ) so if we can get a bound on the divisors we can find its running time . Also for prime numbers (n=a prime number) the inner loop would run two times ! – Pradeep Kumar Aug 20 '17 at 23:27
• @PradeepKumar What you say is lower and upper bounds, I gave the upper bound. Since the lower and upper bounds are quite different, it makes sense to talk about average number of divisors which is $\log{n}$ and so in average it runs for $n\log{n}$ steps. – fade2black Aug 20 '17 at 23:52