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

## leave a comment

## 0 Comments