What is the space complexity of this dictionary in Python?
(1) My Guess: O(V+E) where V is the number of key and E is the maximum length of array value in dictionary.
{
'key' : ['value', 'value2', ...],
'key2': ['value30', 'value31', ...],
...
}
Small Question: If the dictionary is formed of directed graph, should its space complexity be O(2E)?
(2) My Guess: O(V) where V is the number of key.
{
'key' : 4,
'key2': 5,
...
}
Dictionaries in Python are implemented as hash tables.
Typically Hash tables will have n keys and n elements (one for each key). This will give them make them have O(n) space since we can drop constants in O(2n).
What you are trying to do is take a hash table like data structure and have it exhibit behavior it typically does not... The way I understand you are trying to use it is that you have lists of elements and each list can be identified by a key. Since each list can have its own length, a better representation of space complexity is O(k + v1 + v2... + vn), where v1 is the length of list 1 and vn the length of the last list.
If you are using the dictionary as you would use a hash table then the space complexity is O(n).