Can anyone tell me what's the complexity of the below function? And how to calculate the complexity?

I am suspecting that it's O(log(n)) or O(sqrt(N)). My reasoning was based on taking examples of n=4, n=8, n=16 and I found that the loop will take log(n) but I don't think it'll be enough since sqrt also will give the same values so I need to work on bigger values of n, so I am not sure how to approach this.

I had this function in the exam today.

void f(int n){
     int i=1;
     int j=1;
     while(j <= n){
         i  = 1;
         j  = i;
     }
}

CodePudding user response：

The sequence j goes through is 1 3 6 10 15 21, aka the triangular numbers, aka n*(n 1)/2.

Expanded, this is ( n^2 n ) / 2. We can ignore the scaling ( / 2) and linear ( n) factors, which leaves us with n^2.

j grows as a n^2 polynomial, so the loop will stop after the inverse of that growth:

The complexity is O(sqrt(n))

CodePudding user response：

It is depended your condition. In other words, the time complexity is O(log n). How many statements are executed, relative to input size n? Often, but NOT always, we can get an idea from the number of times a loop iterates. The loop body executes for i= 2^0 2^1 2^2 .... 2^n; and this sequence has O(log n) values.

Check the "Introduction to Algorithms" book about more details.