title: Time complexity of set in Java
body: <p>Can someone tell me the time complexity of the below code?</p>
  
  <p><code>a</code> is an array of int.</p>
  
  <pre><code>Set&lt;Integer&gt; set = new HashSet&lt;Integer&gt;();
  for (int i = 0; i &lt; a.length; i++) {
      if (set.contains(arr[i])) {
          System.out.println("Hello");
      }
      set.add(arr[i]);
  }
  </code></pre>
  
  <p>I think that it is <em>O(n)</em>, but I'm not sure since it is using <code>Set</code> and this contains methods as well. It is also calling the <code>add</code> method of <code>set</code>. </p>
  
  <p>Can anyone confirm and explain what the time complexity of the entire above code is? Also, how much space would it take?</p>