0
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ What is your question? Do you want to find the complexity of your C code? What is input? $\endgroup$ – fade2black Aug 20 '17 at 22:12
  • $\begingroup$ Yes I want to find the time complexity of this code ! $\endgroup$ – Pradeep Kumar Aug 20 '17 at 22:13
  • $\begingroup$ 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$? $\endgroup$ – fade2black Aug 20 '17 at 22:18
  • 5
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Aug 20 '17 at 22:23
  • 2
    $\begingroup$ 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. $\endgroup$ – David Richerby Aug 16 '18 at 14:23
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$}))$. $\endgroup$ – xskxzr Apr 14 at 11:14
0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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 ! $\endgroup$ – Pradeep Kumar Aug 20 '17 at 23:27
  • $\begingroup$ @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. $\endgroup$ – fade2black Aug 20 '17 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.