CODEWITHSUNDEEP
algorithmtime-complexity
myfidan
myfidan

Reputation: 17

What is this function time complexity?

is this function complexity O(nlogn)?

find(n){
    for(i=0; i<=n-1; i++){
       for(j=1; j<=i; j=j*2) 
           print("*");
    }
 }

Upvotes: 0

Views: 85

Answers (1)

Osama Ahmad
Osama Ahmad

Reputation: 2096

The complexity of the inner loop is O(log2(i)). The outer loop starts from 0 until n - 1. so the complexity should be log2(1) + log2(2).... log2(n-1) = log((n-1)!). So the complexity is O(log2(n!)).

This is because log(a) + log(b) + log(c)... = log(abc...). In your case it's log(1) + log(2) + log(3)... + log(n-1) = log(1*2*3*...*(n-1)) = log((n-1)!).

O(log n!) approximates to O(n log n) so your complixity is: O(n log n).

Upvotes: 4

Related Questions