In this lecture, we'll complete our algorithm analysis on our tree node and tree classes. We'll start by looking at the AddChild method in the TreeNode class. The Contains method for a list performs a linear search looking for the provided argument. And we know linear searches are order n. So the question is order n in what? Well, order n in the number of children that this particular node has. This line of code is order n, where n is the number of children for the node. The rest of these things are constant time, adding a child is order n if in fact we have to expand the list. And these two are obviously constant time so we have order n here and order n here, which makes the Add(child) operation and order n operation. Removing a node, remember our discussion of Contains? So this is order n in the number of children for the node. So this is order n, where n is the number of children for the node. We null out the parent so this is constant time, but Remove also does a linear search for the node. So this is order n in the number of children. And of course, this is constant time. So we have order n and order n. But including an order n operation in the side an if statement that has an order n boolean expression does not mean we need to multiply them together like we do when we have an order n operation inside a loop that executes n times. So this is still additive. So remove child is still order n. Removing all the children from the node, this loop is clearly order n, where n is the number of children the node has. This is constant time and this is constant time only because we're removing from the end of the list. So we're avoiding any shifting as we go through the list removing stuff. So because the loop executes n times, the RemoveAllChilren operation is order n. And then converting the nodes to a string is also order n in the number of children because we loop over each child printing out its value. For the operations in the tree class, we'll start with the clear method, and let's look at the easy part first. So the easy part is the second loop that executes n times, and RemoveAt is constant time because we're removing from the end of the list. So this chunk of code is order n. This line is constant time. So the question is, what about this? Well, clearly the loop iterates n times where, and it's the number of nodes in the tree. This is constant time. We just talked about RemoveAllChildren as being order n but with the different definition of n, n was the number of children for that particular node. So we have to sort of think of this stuff all together. How many times will we actually remove a child from a parent? And it turns out that, because each node can only have a single parent, we're only going to remove n children in total across all the iterations of this loop. We're only going to remove n total children inside. So we don't have to multiply in order n here times n here to get n squared. It actually turns out that this is order n. So because this is order n and this is order n and this is constant time, clear is an order n operation. To add a node to the tree, this costs us order n in the number of nodes in the tree. This caused us order n in the number of children for the parents node that were adding. And in the worst case, the parent is the root node and all of the children are siblings. They all have the root node as the parent. So in that worst case, this would also be order n in the number of nodes in the tree. Adding a node to the list of nodes is order and if. We have to expand the list. And adding a child is order n, where n is the number of children that the parent has, which in the worst case could be n minus 1 children, where we have a very shallow tree where the root has all the children. And nothing goes lower than those children. So we have a bunch of order ns here, so the add node operation is order n. Removing a node, remember is the most complicated method we have in this class. Luckily to start off with, we have some constant time stuff. We have order n for Clear. We have more constant time stuff. We have order n for removing the child. We have order n for removing the node from the list of nodes because the list Remove method that does a linear search. And then we have this interesting recursion stuff. So everything other than this recursion, which is to recursively prune the subtree, everything else is order n. So we can think of everything else as sort of the body of a loop. It's not really a loop, it's a set of recursions we're going to do but we're going to do order n stuff on every recursion. So the question is, how many recursions are we going to do? And the answer is, in the worst case, we have a tree where every parent has a single node so this is essentially a linked list. And so there's no branching out, so in the worst case, we're trying to remove the node just below the root. And that means that we're going to have to recurse n minus two times to get rid of the rest of the nodes. So the number of recursions is order n and the complexity of the stuff we do inside each recursion is order n. So removing a node is actually an order n squared operation. Finding a particular value in the tree is just a linear search. So this is order n. And converting the tree to a string is also order n because here's where we iterate over all the nodes in the tree. And that means that we're going to have an order n conversion to the string, where n is the number of nodes in the tree. To recap, in this lecture, we got even more practice doing algorithm analysis.
