Big O notation with special inner loop-CodePudding

I would like to have some help regarding analyzing the followings Big O notation.

Case A: The inner loop only runs once in the worst scenario

    for (int i = 0; i < nums.length; i  ) {

       if (i==nums.length-1 && nums[i] == 3){
          for (int j = 0; j < nums.length; j  ) {
           print();
          }
       }
    }

The worst case scenario is an array that finish in 3. Is this O(N) or O(N*N)?

The way I analyse this is the following:

The outer array runs N times= 1(n)
The inner loop in the worst case runs just 1 time = 1

So , n*1 = O(n) , am I ok with the analysis?

Does it makes sense "n*1" or should be "n 1"?

Case B:

The inner loop runs always except if i is the first element

   for (int i = 0; i < nums.length; i  ) {
     if (i!=0){
        for (int j = 0; j < nums.length; j  ) {
          print();
        }
     }
   }

The way I analyse this is the following :

The outer array runs N times= n
The inner loop runs N -1 times =n-1

So , n*(n-1) = O(n*n) , am I ok with the analysis?

I am very confused with those cases, thanks !

CodePudding user response：

Case A:

The outer array runs N times= 1(n)
The inner loop in the worst case runs just 1 time = 1

I think your reasoning here is probably okay, but as it's written this can't be right. The outer array runs N times implies that you count 1 for every iteration of the loop, but The inner loop in the worst case runs just 1 time can't be right (under the same definition), as it will have n iterations as well (in worst-case, ie. if the last element is 3). I think on the first line you used runs = number of iterations and on the second line you used runs = starts/finishes; there's no problem with either, but make sure to be clear and consistent.

You've correctly said that The worst case scenario is an array that finish in 3, and in this case it runs the outer loop n times (skipping over the inner loop) then on the final iteration it doesn't skip the inner loop, which runs n times. This is O(n n) = O(n).

Another way to think of it is that the code could be rewritten as:

for (int i = 0; i < nums.length; i  ) {
}

if ((nums.length > 0) && (nums[nums.length-1] == 3)){
    for (int j = 0; j < nums.length; j  ) {
        print();
    }
}

Which we rewrite for worst-case scenario like so:

for (int i = 0; i < nums.length; i  ) {
}

for (int j = 0; j < nums.length; j  ) {
        print();
}

Then the serial nature of it becomes obvious: n n work. The important thing here is that we haven't changed the algorithm in any important way (we haven't effected the worst-case complexity).

Case B:

Your logic and math here looks good.