I am having trouble understanding how while loops affect the Big O time complexity.

For example, how would I calculate the time complexity for the code below? Since it has a for loop that traverses through each element in the array and two nested while loops my initial thought was O(n^3) for the time complexity but I do not think that is right.

HashMap<Integer,Boolean> ht = new HashMap<>();

for(int j : array){
      if(ht.get(j)) continue;

      int left = j-1;
      //check if hashtable contains number
      while(ht.containsKey(left)){
        //do something
        left--;
      }

      int right = j 1;
      //check if hashtable contains number
      while(ht.containsKey(right)){
        //do something
        right  ;
      }

      int diff = right - left;
      if(max < diff) {
        //do something
      }
}

CodePudding user response：

There is best case, average case, and worst case.

I'm going to have to assume there is something that constrains the two while loops so that neither iterates more than n times, where n is the number of elements in the array.

In the best case, you have O(n). That is because if(ht.get(j)) is always true, the continue path is always taken. Neither while loop is executed.

For the worst case, if(ht.get(j)) is always false, the while loops will be executed. Also, in the worst case, each while loop will have n passes. [1] The net result is 2 * n for both inner loops multiplied by n for the outer loop: (2 * n) * n. That would give you time complexity of O(n^2). [2]

The lookup time could potentially be a factor. A hash table lookup usually runs in constant time: O(1). That's the best case. But, the worst case is O(n). This happens when all entries have the same hash code. If that happens, it could potentially change your worst case to O(n^3).

[1] I suspect the worst case, the number of passes of the first while loop plus the number of passes of the second while loop is actually n or close to it. But, that doesn't change the result.

[2] In Big O, we chose the term that grows the fastest, and ignore the coefficients. So, in this example, we drop the 2 in 2*n*n.

CodePudding user response：

for one nested loop the time complexity works like this: O(n^2).

In each iteration of i, inner loop is executed 'n' times. The time complexity of a loop is equal to the number of times the innermost statement is to be executed.

so for your case that would be O(n^2) O(n).

there you can find more explanation

Time-complexity

CodePudding user response：

Assuming there are m and n entries in your HashMap and array, respectively.

Since you have n elements for the for loop, the complexity can be written as n * complexity_inside_for.

Inside the for loop, you have two consecutive (not nested) while loops, each contributing a complexity of m as in worst case it'll need to go through all entries in your HashMap. Therefore, complexity_inside_for = m m = 2m.

So overall, time complexity is n * 2m. However, as m and n approach infinity, the number 2 doesn't matter because it is not a function of m and/or n and can be discarded. This gives a big-O time complexity of O(m*n)