What is the Time Complexity where loop variable is incremented by 1,2,3,4 of below code?

[ad type=”banner”] 
void fun(int n)
{
   int j = 1, i = 0;
   while (i < n)
   {
       // Some O(1) task
       i = i + j;
       j++;
   }
}

The loop variable ‘i’ is incremented by 1, 2, 3, 4, … until i becomes greater than or equal to n.

The value of i is x(x+1)/2 after x iterations. So if loop runs x times, then x(x+1)/2 < n. Therefore time complexity can be written as Θ(√n).

Categorized in:

Analysis of Algorithm

Tagged in:

, , , , , , , , , , , , , , , , ,