I'm trying to understand why time complexity of accessing a value in a dictionary is O(1).
If I understand correctly, a dictionary is essentially an associative array, i.e. an array A of size n where each element consists of a pair (key, value).
If I give the computer a key, isn't it necessary (in general) to run across the array A in order to find the key and have access to its value? In that case, shouldn't time complexity be O(n)?
Moreover, if the time complexity is O(1) for any dictionary, what's the point of implementing sorted dictionaries (C#, for example)?
My first guess would be that sorted dictionaries make the access faster (by using binary search, for example), but everywhere I look people talk about O(1) in general, so obviously I'm missing something.
If I understand correctly, a dictionary is essentially an associative array, i.e. an array A of size n where each element consists of a pair (key, value).
No. The associative array is typically (ie. almost always) implemented by a hash table. Not an array.
Moreover, if the time complexity is O(1) for any dictionary, what's the point of implementing sorted dictionaries (C#, for example)?
To have them sorted when you needed (hash tables are basically randomly sorted), and more importantly, to answer queries like "first element larger than X" efficiently (in O(log N)).