What is the Time Complexity where loop variable is incremented by 1,2,3,4 of below code?
[ad type=”banner”] [pastacode lang=”c” manual=”void%20fun(int%20n)%0A%7B%0A%20%20%20int%20j%20%3D%201%2C%20i%20%3D%200%3B%0A%20%20%20while%20(i%20%3C%20n)%0A%20%20%20%7B%0A%20%20%20%20%20%20%20%2F%2F%20Some%20O(1)%20task%0A%20%20%20%20%20%20%20i%20%3D%20i%20%2B%20j%3B%0A%20%20%20%20%20%20%20j%2B%2B%3B%0A%20%20%20%7D%0A%7D” message=”” highlight=”” provider=”manual”/]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).