 |
| Source: wikimedia.org |
Let's compare asymptotic time complexity of two following loops:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | int[] _array = Enumerable.Range(0, n).ToArray();List<int> _list = Enumerable.Range(0, n).ToList();//ListChangeByIndexfor (var i = 0; i < n; i++){ _list[i] = i + 1;}//ArrayChangeByIndexfor (var i = 0; i < n; i++){ _array[i] = i + 1;} |
.
.
.
.
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.
