DEV Community

loading...
Cover image for Easy as a pie Big O notation: A note about Objects

Easy as a pie Big O notation: A note about Objects

Elizabeth Villalejos
["Full-stack web dev", "Chihuahua Mom🐶", "Currently Looking for Dev Role"]
・1 min read

An object is an unordered data structure where everything is stored in key-value pairs.

Let superDog = {
Name: “Dulce”,
Breed: “Chihuahua”,
Weight: “2 pounds” }

Objects are great when storing in order is not a concern and we need to be fast at inserting and removing data.

But exactly, how fast?

  • Insertion: O(1)
  • Removal: O(1)
  • Access: O(1)
  • Searching: O(N)

It works in constant time because since we have no order in our data, we technically don’t have a beginning or end so it doesn’t really matter in which order data is added.

Got something to add? Please feel free to reach out for any question, comment or meme.

Discussion (3)

Collapse
pchinery profile image
Philip

I am always happy to see people exploring and explaining theoretical aspects of programming, so thank you very much for that!

I'd like to add one aspect though. "objects" themselves are implemented with other data structures, depending on the programming language used. If you can use them like key value pairs, they will often be implemented using key value pairs. This implies that accessing and removing items can't be O(1) but rather O(log n) like a search in a dictionary. Most likely, adding won't be O(1) as well as hashing is involved and this could lead to collisions, which need to be handled.

If you are using a compiled language (e.g. Java or C#), this will be different, as the compiler knows how to access each of the known items.

I think it can be very insightful to explore the internals of the programming language of choice. Knowing this will help a lot to find hidden complexity in your algorithms.

Collapse
craigmc08 profile image
Craig McIlwrath

Isn't the amortized insertion/lookup/delete complexity for hash tables O(1)? But yeah you are right, it is more complicated.

Collapse
pchinery profile image
Philip

In the average case (and practically), it really is constant access. But as the Big-O notation is about the worst case, so it's about constructing some obscure cases. Hash-based implementations often use buckets based on the result hash. The worst case would be, that all values have the same hash, so we basically end up with a plain list of values with the complexity of lists.

But this does not really apply to the practice and the implementations usually are very optimized, that it should be very hard to even construct such a case practically.

Forem Open with the Forem app