Performance of SortedDictionary vs sorting a Dictionary

Question

I have a list of objects. These objects have many properties including price and quantity. I need to create a new dictionary with key 'price' and value 'quantity'. If two objects have the same price, then the resulting dictionary should have the price as key and the sum of the quantities of both objects as value. As per my knowledge, I can do this in two ways.

1. Using Dictionary data structure, and sort the final dictionary:

var result = new Dictionary<int, int>();
foreach(List<object> obj in list) {
    if(result.ContainsKey(obj.price)) {
        result[price] += quantity;
    }
    else {
        result[price] = quantity;
    }
}
result = result.OrderBy(x => x.Key);

2. Using SortedDictionary:

var result = new SortedDictionary<int, int>();
foreach(List<object> obj in list) {
    if(result.ContainsKey(obj.price)) {
        result[price] += quantity;
    }
    else {
        result[price] = quantity;
    }
}

In the first method, the time complexity for ContainsKey is O(1) and for sorting, order by uses quicksort which has time complexity O(nlogn). So the total time complexity would be O(nlogn). In the second method, the ContainsKey of sortedDictionary already takes O(log n) and as I am repeating this for n times, the total complexity would be O(nlogn). As per my calculation, I feel using both methods should take the same time. Please correct me if I'm wrong. And, if I'm wrong, which method has better performance?

Answer 1

1 will usually be faster. It is easier to sort once than to maintain a sorted dictionary.

Big-O complexity might be the same, but equal complexity does not mean equal performance.

Benchmark results:

|      Method |     Mean |    Error |   StdDev |  Gen 0 | Gen 1 | Gen 2 | Allocated |
|------------ |---------:|---------:|---------:|-------:|------:|------:|----------:|
|        Dict | 361.7 ns |  7.07 ns |  7.26 ns | 0.1554 |     - |     - |     488 B |
| DictOrderBy | 499.9 ns |  9.66 ns |  9.04 ns | 0.2651 |     - |     - |     832 B |
|  SortedDict | 943.7 ns | 18.26 ns | 22.42 ns | 0.2241 |     - |     - |     704 B |

Code: https://gist.github.com/ptupitsyn/71eefbdb607ce3f9ddfae2f5e099184e

Notes:

• TryGetValue eliminates an extra dictionary lookup
• All benchmark methods return results as List in an attempt to make it fair