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*noperations - For the inner loop, we have
n*(n*8)operations - In total, we have
4n + 8n^2operations
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;
}