Would this function be linear, quadratic, or neither? (C#)

Question

In regards to the length of the list being the input (n), would the time complexity of this code be linear because there is only one loop or quadratic due to "any" technically looping through the new array -- but not through every item on every loop? Or would it be neither?

public static List<Item> RemoveDuplicated(List<Item> listToFilter)
{
    var newItemList = new List<Item>();

    foreach(var item in listToFilter)
    {
        if(!newItemList.Any( i => i.ItemId == item.ItemId))
        {
            newItemList.Add(item);
        }
    }
    return newItemList;
}

Answer 1

Algorithm complexity is the asymptotic behaviour as n grows large. If unspecified, we assume the worst-case behaviour. Here, that worst case is where every item is new to the list, such that Any has to traverse the entire existing list.

You nailed those parts: the outer loop executes n times; the inner loop has to traverse that list until it finds the element (we might assume checking m elements, where m is the current list size) or doesn't find it (checking all m elements).

In the worst case, the Any 1+2+3+ ... +(n-1) times, adding each item to the list. I'm sure you recognize this as O(n^2).

Assuming that duplicates are some fixed or bounded proportion of the original list, that expression is dependent on n.

Does that help the understanding?

---

Clarification:

The sum of the sequence 1 .. n is n(n+1) / 2, or (n^2 + n) / 2. This is dominated by the n^2 term.