Identifying time complexity for a loop-CodePudding

I was hoping to have some help in identifying the time complexity of the while loop below. I am trying to solve a problem in o(n) time complexity and was unsure whether this loop would satisfy this condition.

If the loop is not o(n) time complexity would it be o(n^2)?

Thank you :)

int a = 0;
int b = a   1;
while (a < n) {
    b  ;
    if (b == n) {
        a  ;
        b = a   1;
    }
}

CodePudding user response：

(I assume here that the assignment in the if branch is b = a; instead of b = a 1;, otherwise, there is an infinite loop.)

Your algorithm generates all the couples (a, b) such that a < n, b < n and b > a. There are exactly (n - 1) (n - 2) ... 1 couples that satisfy this constraint. (n - 1) (n - 2) ... 1 = (n - 1) * (n - 2) / 2 which gives a complexity in O(n²).

You might be mislead by the fact that there is a single loop in your program which might give the impression that the complexity is O(n), but your algorithm can be rewritten as follows:

int a = 0;
int b;
while (a < n) {
    b = a   1;
    while (b < n) {
       b   ;
    }
    a  ;
}

This makes it easier to see that the complexity is indeed O(n²).

CodePudding user response：

(n)   (n-1)   (n-2)   ...   1 = n*(n-1)/2

So you have an O(n^2) loop.

CodePudding user response：

This is an infinite loop for all values of n in range [1, infinity) because when a will result in value of a equal to n - 1, the value of b will reset to a 1 , which is nothing but n [a 1 => n - 1 1 => n] and in next iteration b will be incremented by 1 and then, theoretically, b == n will never be true.

I am trying to solve a problem in o(n) time complexity....

It would be better if you share some details about the algorithm that you are trying to implement to solve the problem.