title: Time complexities combining
body: <p>Here's a pseudocode procedure that checks whether a list has any duplicates: </p>
  
  <pre><code>duplicates(a,n) {
      t = EmptyTree
  
      for (int i = 0; i &lt; n; i++) {
          insert(a[i], t)
      }
  
      if (isIn(EmptyTree, t))
          return true
      else
          return false
   }
  </code></pre>
  
  <p>a is the array being checked, n is the length of the array. insert and isIn both have time complexities O(log2n) (this being log to base 2). My question is, what would be the average case and worst case time complexity of the whole duplicates procedure? I'm thinking it should be O(log2n) for both as both insert and isIn have this time complexity, but what's throwing me off is the for loop as it calls insert for every element - does this mean the procedure will be O(n) instead, as that's the time complexity of the for loop?</p>
  
  <p>EDIT: adjusted procedure</p>
  
  <pre><code>duplicates3(a,n) {
      t = EmptyTree
  
      for (int i = 0; i &lt; n; i++) {
          insert(a[i], t)
  
          if (isIn(EmptyTree, t))
              return true
      }
  
      return false
   }
  </code></pre>