What’s faster in C#: setting an array by index or a generic list by index? Are you sure you know the correct answer?

Credits: 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();

//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.

From previous blog...

I recommend a nice article regarding .NET collections complexity: http://c-sharp-snippets.blogspot.com/2010/03/runtime-complexity-of-net-generic.html

Konrad Kokosa Comment from previous blog

Indeed a must-read for every .NET pro. Here is another, simillar article: http://www.growingwiththeweb.com/2013/02/what-data-structure-net-collections-use.html

Me Comment from previous blog