Skip to content

BigO calculation for duplicate finder #7

@sonerfromnurland

Description

@sonerfromnurland

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;
}

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions