BigO Calculation of Loops

62 Views Asked by At

I'm reading the BigO calculation. For the following snippet, for the worst-case scenario of the inner loop, n*(n*8) is given, but for the outer loop, 4n is given. If 4 is the operation count of the outer for loop (1 for assignment, 1 for comparison, and 2 for incremental, respectively), why don't we apply the same logic to the inner one? That is, 8*n for the inner loop and 4*n for the outer loop. Shouldn't the outcome be 32n^2? However, the book says (albeit seeming wrong to me)

The worst case is when the array doesn't contain duplicates and is of size n (= numbers.length):

  • For the outer loop, we have 4*n operations
  • For the inner loop, we have n*(n*8) operations
  • In total, we have 4n + 8n^2 operations
public boolean containsDuplicates(int[] numbers) {
     for (int i=0; i<numbers.length; i++) { // 4 operations
       for (int j=0; j<numbers.length; j++) { // 4 operations
         if (i != j && numbers[i] == numbers[j]) return true; // 4 operations
} }
  return false;
}