Your assumption is right. You can find the complexities of the operations documented on MSDN:
List<T>.Insert:
This method is an O(n) operation, where n is Count.
List<T>.Add:
If Count already equals Capacity, the capacity of the List is increased by automatically reallocating the internal array, and the existing elements are copied to the new array before the new element is added.
If Count is less than Capacity, this method is an O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.
Yes, the capacity is increased as needed, but no, the capacity is not increased for every Add operation. As we can see in the documentation of the constructor in the reference source, lists have a certain base capacity, and the capacity is doubled every time it is exceeded:
// Constructs a List. The list is initially empty and has a capacity
// of zero. Upon adding the first element to the list the capacity is
// increased to 16, and then increased in multiples of two as required.
public List() {
...
}
So, in a nutshell, choosing the right list depends on your needs. This answer compares the complexities of common operations in array-based lists (such as List<T>) and linked lists (such as LinkedList<T>):
