title: What is the Big O notation of this method?
body: <p>I have run across this method in our code base and wonder what the Big O is.  The method takes a flat list and creates a tree, assigning the Parent and Children values as it goes.</p>
  
  <pre><code>private void AddChildren(Group group, IEnumerable&lt;Group&gt; groups)
  {
      foreach (var g in groups)
      {
          if (g.ParentId == group.Id)
          {
              g.Parent = group;
              group.Children.Add(g);
              AddChildren(g, groups);
          }
      }
  }
  </code></pre>
  
  <p>It's been a while since I have done Big O outside of identifying straight forward n^2 (or worse) methods, but my take on it goes like this:</p>
  
  <ul>
  <li>We are iterating every node in the list, giving us n</li>
  <li>We are using a conditional to process a subset of the items being iterated.  There can be multiple matches here and don't know how to express that number, or how it modifies the recursive call to AddChildren</li>
  <li>We have some simple assignments, and I don't know if that warrants a +1 modifier</li>
  <li>We are recursing but it's not for every item in the enclosing iteration</li>
  </ul>
  
  <p>Just tossing something out there so I can see if I was in the ballpark:</p>
  
  <p>n + (x * n) </p>
  
  <p>where x is the number of matches in the if loop. </p>
  
  <p>Any thoughts on what this actually is would be great, thanks.</p>