In this lecture, we'll complete the algorithm analysis, on the operations, our methods in our linked list, and linked list node classes. We'll start by evaluating the complexity of the clear method in the link list parent class. And remember that this piece, right here, walks the entire list, touching each node to disconnect that node from the next node in the linked list. And that means that this while loop, right here, executes N times, where N is the number of nodes in the linked list. The rest of these lines of code are constant time, order one operation, but this while loop makes the clear operation an order N operation. To remove an item from the linked list, this is constant time, this is constant time, this is constant time, these are constant time. So, here we walk the list, looking for the node that we want to remove. And because the node might be at the very end or the node might not be in the list at all, this while loop executes in the worst case N times. And that means that this chunk of code is order N, the rest of this stuff is constant time. So, this while loop makes the remove operation order N. To find the particular node in the list, again we have a while loop that walks the list. And, again, the worst case is the node is at the very end of the list or not in the list at all, in which case is while loop executes N times. So, this operation, because everything else is order one, this operation is also order N. Finally, converting the list to a string. As you might expect, this part where we keep walking the list until we reach the end means that we touch every node to appended value to the string, and that means that this is also an order N operation. The only other thing to look at, is the add method in the unsorted link list and in the sorted link list. Adding an item to an unsorted linked list, this is constant time, this is constant time, this is constant time, and this is constant time. So, the add operation is an order one operation. And this is better than adding to a dynamic array, remember, because when we needed to expand the dynamic array, we needed to pay the cost of expanding the array and copying each element over. So add was sometimes an order N operation, even for an unordered dynamic array. And for our unsorted linked list, adding is always constant time. That is not true for the sorted linked list. We checked for the empty list constant time, constant time, constant time, constant time. Here is the piece that is not constant time. We have to iterate over the list, looking for the appropriate place to add our new node. And in the worst case, our new node needs to go at the very end of the list and that means that this while loop executes N times as we walk the list looking for where we should put the new item. So, because everything else is order one, the add operation first sorted linked list is an order N operation. To recap, in this lecture we got more practice doing algorithm analysis, and we saw again, how the number of loop iterations has a major impact on the complexity of our algorithms.