In different coding competitions, there is a constraint of O(n). So, I thought of implementing using a single while loop that works as nested for loop. Would I be able to bypass the constraint or not in competitive coding platforms. Code:

#include<bits/stdc  .h>
using namespace std;

int main(){
    int i=0, j=0, n;
    cin>>n;

    while(i<n && j<n){
        cout<<i<<" "<<j<<endl;

        if(j==n-1){
              i;
            j=0;
        }
        else{
            j  ;
        }

    }

    return 0;
}

CodePudding user response：

You can also say that your algorithm runs in constant-time O(1) with respect to

n = the number of coffee cups drunk by Stackoverflow users.

As the number of coffee cups grows, your code still takes the same time to run. This is a perfectly correct statement.

However, those constraints you talk of specify a maximum time-complexity with respect to some given, or understood, variable n. Usually the size of the input to your program, again measured in some way that is either explicitly given or implicitly understood. So no, re-defining the variables won't get you around the constraints.

That said, writing a nested loop as a single loop, such as in the way you discovered, is not useless as there are situations where it might come in handy. But no, it will not improve your asymptotic complexity. Ultimately, you need to count the total number of operations, or measure the actual time, for various inputs, and this is what will give you your time complexity. In your case, it's O(n²) with respect to the value of n given to your code.

CodePudding user response：

You can't determine complexity by counting loop depth. Your code is still O(n²) (where n is the given value n), because j will be modified n², and in fact it will even print out n² lines.

To determine complexity, you need to count operations. A lot of times, when you see two nested loops, they will both do O(n) iterations, and O(n²) time will result, but that is a hint only, not a universal truth.