Order of a simple code

Question

Today I have a discussion with my boss about order of my code, but we can't agree about time complexity of my code. I believe that my code is of O(n), but my boss doesn't accept.

What is your idea about order of this code?

void Process(Node currentNode)
{
    Print(currentNode.Title); //O(Print)=O(1)
    foreach(Child child in currentNode.Children)
    {
        Process(child);
    }
}

---

EDIT1

Multiple Nodes doesn't share the same child Node. I have a tree. Children is a simple list of Node so that its members can easily be visited in liner time.

You can see here the implementation of Node class:

class Node
{
    public string Title{get;set;}
    public List<Node> Children{get;set}
}

Answer 1

If this is a tree and n is the number of nodes in the tree...

Then yes, it's O(n).

It's fairly easy to see that we only do a constant amount of work per node.

Each node will only be a child to one other node, thus it will only appear in the for-loop once. And since a for-loop iteration, excluding the recursive call, takes O(1), we can see that the for-loop part of the recursion (for all the calls) takes in O(n). And the rest of the function is clearly O(1), and, from the definition of a tree, we can see that we'll only execute the function once per node, thus O(n) times.

Thus the total running time is O(n).

Note: I'm assuming Children is something that can be enumerated in linear time. If this is not true, the running time would be the same as how long it takes to enumerate it. More specifically, the worst-case will be when one node has the remaining n-1 nodes as children (and none of the other nodes have children). I think the proof of this will distract a bit from the point, so I'll leave that for another day.

---

If it's not a tree, i.e. multiple nodes can have the same children, or there is a cycle, it's not O(n). In the case of a cycle, it wouldn't terminate. If multiple nodes can have the same children, but there isn't a cycle, the running time would be exponential - the root can have n-1 children. One of those children can have n-2 children, one of which can have n-3 children, etc.

Answer 2

I believe that the time order is O(N) where N is the total number of descendants of the element you're Processing. This is because for each descendant, you Print. If you do an O(1) task N times, that's O(N).

Answer 3

It really depends on how currentNode.Children is actually implemented (or what is the underlying backing data structure).

.Children can easily be a property that returns its own enumerator with its own implementation, and time complexity would simply depend on the custom enumerator algorithm.

On the surface it does look like it can be O(N), but post definition/implementation behind .Children property, and it should be possible to give a more definitive answer. At this point, there is not enough information to say definitively.