CODEWITHSUNDEEP
pythonperformance
merry-go-round
merry-go-round

Reputation: 4615

Space Complexity for dictionary in Python3

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,
    ...
}

Upvotes: 5

Views: 9579

Answers (1)

Bilal Saleem
Bilal Saleem

Reputation: 633

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

Upvotes: 4

Related Questions