CODEWITHSUNDEEP
time-complexity
Hosna
Hosna

Reputation: 29

finding time complexity of an algorithm with loops

well I'm facing some problems finding the time complexity of the algorithm below. though it seemed easy at first sight... the result would be different each time based on the input.

 for(int i=2; i<=n; i++){
    for(int j=2; j*j<=i;j++){
        if(i%j==0){
            k++;
            break;
        }
    }
}

Upvotes: 1

Views: 84

Answers (1)

Schwern
Schwern

Reputation: 165546

Short answer: it's O(nlogn).

for(int i=2; i<=n; i++) is easy, that's O(n). Starting at 2 makes no difference.

for(int j=2; j*j<=i;j++) will grow 4, 9, 16, 25 meaning it will run roughly sqrt(n) times. So those two are O(nlogn).

The final twist is if(i%j==0) { break }. Since j starts at 2 this means when i is even there will only be one iteration. When i is divisible by 3 there will only be 2 iterations. When i is divisible by 5 there will only be 4 iterations. This is interesting, but it doesn't fundamentally change the nature of the inner loop.

Empirical testing shows this to be close enough for time complexity.

n = 2, iterations = 0, n*ln(n) = 1, n*log2(n) = 2
n = 4, iterations = 1, n*ln(n) = 6, n*log2(n) = 8
n = 8, iterations = 5, n*ln(n) = 17, n*log2(n) = 24
n = 16, iterations = 17, n*ln(n) = 44, n*log2(n) = 64
n = 32, iterations = 50, n*ln(n) = 111, n*log2(n) = 160
n = 64, iterations = 130, n*ln(n) = 266, n*log2(n) = 384
n = 128, iterations = 337, n*ln(n) = 621, n*log2(n) = 896
n = 256, iterations = 858, n*ln(n) = 1420, n*log2(n) = 2048
n = 512, iterations = 2175, n*ln(n) = 3194, n*log2(n) = 4608
n = 1024, iterations = 5472, n*ln(n) = 7098, n*log2(n) = 10240
n = 2048, iterations = 13821, n*ln(n) = 15615, n*log2(n) = 22528
n = 4096, iterations = 35166, n*ln(n) = 34070, n*log2(n) = 49152
n = 8192, iterations = 89609, n*ln(n) = 73817, n*log2(n) = 106496
n = 16384, iterations = 229956, n*ln(n) = 158991, n*log2(n) = 229376
n = 32768, iterations = 591087, n*ln(n) = 340696, n*log2(n) = 491520
n = 65536, iterations = 1531519, n*ln(n) = 726817, n*log2(n) = 1048576

int foo(int n) {
    int k = 0;

    for(int i=2; i<=n; i++){
       for(int j=2; j*j<=i;j++){
           k++;

           if(i%j==0){
               break;
           }
       }
    }

    return k;
}

int main() {
    for(int n = 2; n < 100000; n *= 2) {
        printf("n = %d, iterations = %d, n*ln(n) = %.0f, n*log2(n) = %0.f\n",
            n, foo(n), log(n)*n, log2(n)*n
        );
    }
}

Upvotes: 1

Related Questions