Time Complexity where loop variable is incremented by 1, 2, 3, 4 ..- Learnengineeringforu

Time Complexity where loop variable is incremented by 1, 2, 3, 4 ..

What is the time complexity of below code?

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).

This article is contributed by Piyush Gupta. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above