 |
| Source: wikimedia.org |
Let's compare asymptotic time complexity of two following loops:
int[] _array = Enumerable.Range(0, n).ToArray();
List<int> _list = Enumerable.Range(0, n).ToList();
//ListChangeByIndex
for (var i = 0; i < n; i++)
{
_list[i] = i + 1;
}
//ArrayChangeByIndex
for (var i = 0; i < n; i++)
{
_array[i] = i + 1;
}
How do you think, which one is faster?
.
.
.
.
Many developers think the fist one will be slower, because in each loop computer is forced to visit all nodes from 0 to i to finally set the variable.
.
.
.
.
However, that's not the case. Both loops have O(n) complexity. That's because in the .NET source we can clearly see that's underlying data structure for a List<T> is an array: list.cs. Therefore, those two loops are essentially equal.
