1

I have this for loop:

public void method(int[] arr) {
    Set set = new HashSet();

    for(int i = 0; i < arr.length; i++){
        set.add(arr[i]);
    }
}

is this method in O(n)?

hamid
  • 2,033
  • 4
  • 22
  • 42

2 Answers2

4

If you use a HashSet, yes. HashSet has O(1) and you multiply it with O(n) by using a for-loop. Thus, the whole construct has O(n).

poitroae
  • 21,129
  • 10
  • 63
  • 81
-1

HashSet has a near-linear insertion performance, so yes: n such operations would be O(n).

Note that I would do this instead, which achieves exactly the same result as what all your code does:

Set<Integer> set = new HashSet<Integer>(Arrays.asList(arr));

You shoukd type your Set too, as above.

Bohemian
  • 412,405
  • 93
  • 575
  • 722
  • But `Set`will have the size of one and I agree with typing the `Set.` – hamid Mar 17 '13 at 10:03
  • What do you mean? This code achieves exactly what your code does. – Bohemian Mar 17 '13 at 10:05
  • No, in my code, for [1,2,3] `set` has the size of 3. But your code the size is always one! – hamid Mar 17 '13 at 10:07
  • It's been so long since I used an untyprd list... You need to type it - you should anyway. See edited answer. – Bohemian Mar 17 '13 at 10:08
  • The code you've posted won't compile because `Arrays.asList` doesn't work usefully with arrays of primitives. (It will box the argument into an `int[][]` and return a `List`, which will then be incompatible with the `HashSet`). – Boann Nov 23 '15 at 18:39