Data-Structures-and-Algorithms-in-Java icon indicating copy to clipboard operation
Data-Structures-and-Algorithms-in-Java copied to clipboard

BigO calculation for duplicate finder

Open sonerfromnurland opened this issue 1 year ago • 0 comments

I'm reading the BigO calculation on page 19, on which, 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), 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?

public boolean containsDuplicates(int[] numbers) {
     for (int i=0; i<numbers.length; i++) {
       for (int j=0; j<numbers.length; j++) {
         if (i != j && numbers[i] == numbers[j]) return true; // 8 operations
} }
  return false;
}

sonerfromnurland avatar Jun 03 '23 13:06 sonerfromnurland