But why would you square n? You're only doing each operation once.Originally Posted by sethjackson
From what I saw on that site:
Remove all nodes = O(n)
Add new nodes = O(m)
O(n) + O(m) = O(n + m)
But why would you square n? You're only doing each operation once.
From what I saw on that site:
Remove all nodes = O(n)
Add new nodes = O(m)
O(n) + O(m) = O(n + m)
Clearing is a linear operation. Linear = O(n)
Cloning the nodes is also Linear because you have to iterate through each node of the other list.
O(N2) says that the algorithm's performance is proportional to the square of the data set size. This happens when the algorithm processes each element of a set, and that processing requires another pass through the set. The infamous Bubble Sort is O(N2).
That would be true if you add all elements of List B to List A for each element in List A that you remove.
