Python Big O: the time complexities of different data structures in Python ( www.pythonmorsels.com )

Trey Hunner writes:

This article is primarily meant to act as a Python time complexity cheat sheet for those who already understand what time complexity is and how the time complexity of an operation might affect your code. For a more thorough explanation of time complexity see Ned Batchelder's article/talk on this subject.

Read Python Big O: the time complexities of different data structures in Python

sugar_in_your_tea ,

sorted_sequence.index(item)

Shouldn't this be O(n log n)? I guess Python doesn't have a list that stays sorted.

As a workaround, just use dict keys with no values instead.

Nomecks ,

Sets stay sorted, no?

sugar_in_your_tea ,

Nope, sets are unordered.

Nomecks ,

Ah, sorry. Sets are unique, not ordered. Thanks!

sugar_in_your_tea ,

Yeah, I just think it's kind of odd though. If a language only has lists and hash maps, my go-to is to use a hash map for uniqueness, and sort the list for ordered lists.

But in Python, it's backwards where I use the hash map (dict) for ordered data and the set for uniqueness, because hash maps are unordered in most languages I've used.

cyrl ,

Cheers, always good to be aware of these concepts even if Pythons is far from 'blazingly fast'

RobotToaster ,
@RobotToaster@mander.xyz avatar

Damn, I was hoping someone had python running a Megadeus.

ericjmorey OP ,
@ericjmorey@programming.dev avatar

I don't know what that means

Midnitte ,

Big O notation or something I'm not a compsci

  • All
  • Subscribed
  • Moderated
  • Favorites
  • •
  • [email protected]
  • kbinchat
  • All magazines
    •