I have written two programs to find the number of divisors of a number.

The first function has less code than the second one but for a number like 500 000, it make 250 001 iterations.

However the second function which has more code make 800 iterations.

Which function is more efficient than the other regarding time complexity ?

int divisors(int n) 
{
  int i, count = 1;
  
  for (i = 1; i <= n / 2; i  ) 
  {
    if (n % i == 0)
      count   ;
  } 
  
  return count;
}


 int divisors(int nbr)
 {
    int div_1=1;
    int div_2=0;
    int n_div=0;
    
    
    do {
        
        if (nbr % div_1 == 0)
        {
            div_2 = nbr / div_1;
            if(div_1==div_2)
            {
                n_div =1;
            }
            else
            { n_div = 2; }
        }
        div_1   ;

    }while(div_1<div_2);

    return n_div;
}

CodePudding user response：

The first is O(n) with its for (i = 1; i <= n / 2; i ).

The second is O(sqrt(n)) with its div_2 = nbr / div_1; and }while(div_1<div_2); - a lower time complexity.

With large enough n, the 2nd is more time efficient.

Note: Both loops use a a % b - a somewhat expensive operation. The second uses a a / b - another somewhat expensive operation. A good compile will see these two nearby operations and perform them both for the about the cost of one.

Perhaps a 3rd alterative? (Also O(sqrt(n)) )
This uses div() to compute the quotient and remainder in one operation for weak compilers that do not fold a common /, % together. It moves the div_1==div_2 to outside the loop as it never true more than once.

#include <stdlib.h>

// Untested illustrative code.
int divisors3(int nbr) {
  int count = 0;
  int divisor = 1;
  div_t qr = { .quot = n };
  // Add 2 to the count for the distinct divisor and quotient.
  while (divisor < qr.quot) {
    if (qr.rem == 0) {
      count  = 2;
    }
    divisor  ;
    qr = div(nbr, divisor);
  }
  // Add 1 to the count for the common divisor and quotient.
  if (divisor == qr.quot) {
    if (qr.rem == 0) {
      count  ;
    }
  }
  return count; 
}

More efferent code could take advantage of divisor being a multiple factor of nbr.