0

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 } }
Improve this question
2
  • 1
    O(n^3) would be applicable if you have three nested loops. You only have two levels of nesting, as the inner loops are side-by-side, not nested. Commented May 26, 2022 at 2:11
  • It looks to me that we don't have enough information to evaluate either of the two while loops. There must be some something that constrains how far right and left can go, but we don't know what. For all I know, there is a bug, and one or both of the while loops are infinite loops. Commented May 26, 2022 at 2:47

3 Answers 3

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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)

Improve this answer

Comments

0

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

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.