How can the time complexity (asymptotically) be equal for these functions?

Question

They differ in actual running time I know but using the concept I cannot determine, since the codes are drastically different in execution, how they have the same time complexity.

How come

void fun(){
    int i, j;
    for (i=1; i<=n; i++){
        for (j=1; j<=log(i); j++){
            printf("GeeksforGeeks");//prin tit
        }
    }
}

and

void fun2(){
    int i, j;
    for (i=1; i<=n; i++){
        for (j=1; j<=log(n); j++){
            printf("GeeksforGeeks");//print it
        }
    }
}

are asymptotically the same and have a time complexity of O(logn!)?

Possible duplicate of [Show that the summation ∑ i to n (logi) is O(nlogn)](http://stackoverflow.com/questions/21152609/show-that-the-summation-%e2%88%91-i-to-n-logi-is-onlogn) — Paul Hankin, Oct 14 '16 at 11:14

score 1 · Accepted Answer · answered Oct 14 '16 at 08:00

1

The number of steps for fun is O(sum of log(i) for i from 1 to n) which is the same as O(log(n!)).

The number of steps for fun2 is O(n log(n)).

Now Stirling's approximation tells us that this is actually the same.

answered Oct 14 '16 at 08:00

Henry

42,982
7
68
84

yep! `log2(n!) = Θ(n · log2(n))` you could look at this as i = `O(n)` and therefore they behave the same. – yd1 Oct 14 '16 at 08:43

How can the time complexity (asymptotically) be equal for these functions?

1 Answers1