# c# - What is the Complexity of N-ary tree insertion and searching?

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:

Structure:

``public class Node{public int Value { get; set; }public Node Children { get; set; }public Node Sibilings { get; set; }}``

This method for searching:

``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;}``

This method for insertion:

``public void Add(int[] data){Node temp = null;temp = search(ROOT, data);if (temp == null)temp = new Node(data);if (this.ROOT == null)ROOT = temp;Node parent = temp;for (int j = 1; j <= this.NoOfChildrens; j++){// for first childif (j == 1){parent.Children = new Node(data[j]);parent = parent.Children;}//for all other childselse{parent.Sibilings = new Node(data[j]);parent = parent.Sibilings;}}}``

Program entry point:

``static void Main(string[] args){NAryTree naryTree = new NAryTree(3);// 1st element in each row is node Value,>=2nd....=>value of childint[][] 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);naryTree.Add(data);naryTree.Add(data);naryTree.Add(data);naryTree.Add(new int[] {10,3,6,4});naryTree.preorder(naryTree.ROOT);Console.ReadLine();}``

What is the bigO complexity of these methods?

Let's see what we have in `Search` method. It is not a binary tree and we have recursion. So the `Search` method will call `N` times till we find a necessary value. So we can conclude that we have O(N) where `N` is the maximum(worst) number of iteration to find a value at the last iteration:

``````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;
}
``````

For Addition method is simpler as we have `for` statement and no nested loops. So we have `O(N)` for `Addition` method.

As Wisconsin university says:

So for loops for (i = 0; i < N; i++) { sequence of statements } The loop executes N times, so the sequence of statements also executes N times. Since we assume the statements are O(1), the total time for the for loop is N * O(1), which is O(N) overall.