title: What is the Complexity of N-ary tree insertion and searching?
body: <p>I am implementing an N-1ry tree in C#. I am wondering how can I calculate the complexity of below methods. Here is my code:</p>
  
  <p>Structure:</p>
  
  <pre><code>public class Node
  {
      public int Value { get; set; }
      public Node Children { get; set; }
      public Node Sibilings { get; set; }
  
  }
  </code></pre>
  
  <p>This method for searching:</p>
  
  <pre><code>public Node search(Node root, int data)
  {
      if (root == null)
          return null;
  
      if (data == root.Value)
          return root;
  
      Node t = search(root.Children, data);
      if (t == null)
          t = search(root.Sibilings, data);
      return t;
  }
  </code></pre>
  
  <p>This method for insertion:</p>
  
  <pre><code>public void Add(int[] data)
  {
      Node temp = null;
      temp = search(ROOT, data[0]);
  
      if (temp == null)
          temp = new Node(data[0]);
  
      if (this.ROOT == null)
          ROOT = temp;
      Node parent = temp;
  
      for (int j = 1; j &lt;= this.NoOfChildrens; j++)
      {
          // for first child
          if (j == 1)
          {
              parent.Children = new Node(data[j]);
              parent = parent.Children;
          }
          //for all other childs
          else
          {
              parent.Sibilings = new Node(data[j]);
              parent = parent.Sibilings;
          }
  
      }
  
  }
  </code></pre>
  
  <p>Program entry point:</p>
  
  <pre><code>static void Main(string[] args)
  {
      NAryTree naryTree = new NAryTree(3);
  
      // 1st element in each row is node Value,&gt;=2nd....=&gt;value of child
  
      int[][] data = { new int[] { 1, 2, 3, 4 }, new int[] { 2, 1, 6,0 }, new int[] { 3, 8, 9, 10 }, new int[] { 4, 0, 0, 0 } };
  
      naryTree.Add(data[0]);
      naryTree.Add(data[1]);
      naryTree.Add(data[2]);
      naryTree.Add(data[3]);
      naryTree.Add(new int[] {10,3,6,4});
  
      naryTree.preorder(naryTree.ROOT);
      Console.ReadLine();
  }
  </code></pre>
  
  <p>What is the bigO complexity of these methods?</p>