Data-Structures-and-Algorithms-in-Java
Data-Structures-and-Algorithms-in-Java copied to clipboard
BigO calculation for duplicate finder
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;
}