[inertiatic]

>The N in O(N) is the number of elements already in the collection, not the number of items you are inserting.

For a hashmap, the operation of inserting N items is O(N) and yes that N is the number of items you are inserting. So flat out wrong on that one.

The rest is kind of obvious.

[ModernMech]

"For a hashmap, the operation of inserting N items is O(N) and yes that N is the number of items you are inserting."

This is not a proper application of big O notation. Big O notation is asymptotic. It's a shorthand for considering the performance of the algorithm as the number of elements tends to infinity. If you insert a single item into a linked list we don't say that is O(1) because it's a single item; you still need to iterate over N items already in the list before you can insert it. The more items in the list, the more items you have to iterate over before the insertion occurs.

But if you don't believe me about the hash map, here's an algorithm for inserting in C++ using linked lists for collision resolution:

  template <class T>
  bool HashSet<T>::insert(T item) {
      // Hash the item
      unsigned long ix = this->hash(item);
      // Find the item in the appropriate bucket. If it's already there, return false.
      if (this->array[ix]->findItem(item) != -1) {
          return false;
      }
      // If the item is not in this bucket, insert it.
      this->array[ix]->insertAtHead(item);
      return true;
  }

The only linear-time operation in this algorithm is findItem() on the linked list, but for a properly sized hash table, the linked list in question here should have very few items in it compared to the rest of the table (n_linked_list << N_hash_table). insertAtHead() is O(1) always. hash is O(1) always. The one thing missing in this example is resizing the table if it gets too full, which is O(N) and generally requires re-hashing all the items. Ideally you could make the table large enough when you initialize it to avoid this altogether, and then you can maintain that O(1) insertion time. This is why O(1) is the best case, while O(N) is the worst case. But O(1) should also be the common case.

Therefore if I have 1 item in my hash table or 1 million, it's still going to take the same amount of time to insert the next item. That's what we mean when we say inserting in a hash map O(1); it will take the same amount of time to insert the first item as the millionth item. Even though, yes, you have to call insert a million times. That's obvious. But that's not what asymptotic complexity analysis and big O notation is for.

With something like a linked list, if you try to insert a million items, it will be fast for the first one and slow for the millionth one (if you are inserting without a tail pointer). The rate at which it gets slower is linearly proportional to the number of items in the list. That's what we mean when we say inserting into a linked list is O(N).

If you still think inserting into a hash table is O(N), then answer me this: what's even the point of a hash table?

[inertiatic]

My guy, we're talking about inserting N items to a data structure. Or executing an algorithm where the input is a set of N items.

The N here is the number of items you're inserting.

There's another number that we can consider a constant that's irrelevant to this analysis, M, the number of items in the data structure. M doesn't affect the complexity, as don't other numbers you can come up with, like D, the number of donuts you ate today. The complexity of our algorithm in this case is unaffected by changing these numbers.

An algorithm's complexity is talked to in terms of its input. Not in terms of if my input wasn't actually N sized but it was 1 and instead another hidden input which is the pre-existing data structure was sized N.

So, now, the algorithm of inserting a set of N items to a hash map is O(N), because it's broken down into N independent operations where each is constant time.

Same as, despite addition being constant time, the algorithm of adding the N items of a set is O(N).

[ModernMech]

Okay, I see where you're confused. You're saying the following algorithm is O(N)

  for n in N
    hashset.insert(n)

Which... okay, but that's not exactly what big O notation is for, because it doesn't tell us anything about insert(). It's not a useful analysis, of this code, because it's the same for any set of N items. The algorithm for inserting into a list is the same

  for n in N
    list.insert(n)

Okay, so does this mean inserting into a hash set and a list have the same computational complexity? No, of course not. In your post you've already admitted my point: "it's broken down into N independent operations where each is constant time." Inserting into a hash set is constant time. Agreed.

> "The N here is the number of items you're inserting...There's another number that we can consider a constant that's irrelevant to this analysis, M, the number of items in the data structure. M doesn't affect the complexity"

Take this example. Let's say I have a linked list of M = 1 million items, and I want to insert N = 2 items into this list (without a tail pointer). How many iterations will I have to do: N, or NM? It's the latter of course.

But you've just told me the only thing I have to think about when analyzing an algorithm's complexity is the input set. The number of items in the list doesn't matter. Clearly that's not the case given this example.

Let's think about the hash set. I have M = 1 million items in the hash set and N = 2 items I want to insert. How many iterations will I have to do, 2 or 2 million? For a good hash set, just 2. Now, does this mean that inserting into a hash set is O(N) because N = 2? No, that's a misuse of asymptotic complexity analysis, because again, the N in this notation is thought to be tending to infinity. Since N << M we say the complexity of this algorithm is O(1). As the number of items in the data structure grows, the amount of time inserting doesn't change, even though you have to loop over N items to insert each one into the list.

> An algorithm's complexity is talked to in terms of its input. Not in terms of if my input wasn't actually N sized but it was 1 and instead another hidden input which is the pre-existing data structure was sized N.

Yes, but you can't stop your analysis of a data structure there, because the data structure has state. As you process the input set, the set inside the data structure grows, and depending on the data structure, this will change the overall complexity of the algorithm.

You can't say that we just consider the input set, because then there's no such thing as a constant time algorithm, since you always have to loop over N items at minimum. In a proper asymptotic complexity analysis of a data structure, it's absolutely essential to consider M, the number of elements in the data structure, what happens when you add an additional element, and how that changes over time. Otherwise, all algorithms are O(N) at minimum, and there's no such thing as a data structure that gives constant time insert.

As I asked you before, if inserting into a hash set is O(N), what's the point of a hash set? Because inserting into a list is O(N), so why would I ever use a hash set over a linked list? What is even the point of this data structure?