0
#include <stdio.h>
int f(int (*d)[2], int n)
{
      int p = 0, cnt;
      for (int i=2; i*i <= n; ++i)
      {
             for (cnt = 0; n % i == 0; cnt++, n /= i) {}
             if (cnt == 0)
                  continue;
             d[p][0] =  i;
             d[p++][1] = cnt;
      }
      if (n > 1)
      {
             d[p][0] = n;
             d[p++](l] = 1;
      }
      return p;
}

So as far as I understand when I m looking for complexity, I m looking for loops. The first loop is trivial. It gives us O(sqrt(n)), but there is a second loop which decreases n, I don t really understand this moment. Experiments show that complexity is O(log(n)).

klutt
  • 30,332
  • 17
  • 55
  • 95
Hmmman
  • 47
  • 5
  • Possible duplicate of [What is a plain English explanation of "Big O" notation?](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) – Patrick Jan 28 '19 at 15:49
  • It depends on n for prime n its sqrt(n) for highley composite numbers its log(n) for others it depends. So it's O(sqrt(n)) but not Theta(sqrt(n)). – kingW3 Jan 28 '19 at 15:57
  • Why do you need to know? This particular example looks like something where I would be completely satisfied with a value from just testing it, without theoretical calculations. – klutt Jan 28 '19 at 16:20
  • And to the question "how can i fast identify complexity in any code" the answer is, you cannot. There is no magic bullet. The more skilled you are, the faster you can figure it out. – klutt Jan 28 '19 at 16:21

1 Answers1

0

Speaking of the second loop : n % i == 0; and n=n/i; if we loop in the for loop we will have in the first iteration n=n/i/i .... in the k iteration we are going to have n/(i^k) and this will stop when n%i!=0; lets say n/(i^k)==1 so 1%i==1 !=0 so from n/(i^k)==1 we are going to have k=log(n) in i base which mean log(n)

Spinkoo
  • 2,080
  • 1
  • 7
  • 23