Accidentally quadratic! Don't fall for this common big O mistake! Python's syntax is short and sweet, sometimes it can be easy to forget the performance implications of little things like "in". These can add up in unexpected ways even if performance is not high on your priority list. *Important Notes*: 1. list_in and set_in are creative pseudo-code and not a good representation of how CPython actually implements these operations in C. 2. O(1) runtime for x in set depends on having a good hash function so that probing "the" spot that x should go is O(1). 3. Python has variable width integers, so seemingly constant time operations like adding or multiplying by an integer (e.g. total += n) are technically not constant time, and you will see this effect if your ints get big enough. ― mCoding with James Murphy (https://mcoding.io/) Source code: https://github.com/mCodingLLC/VideosSampleCode CPython time complexities: https://wiki.python.org/moin/TimeComplexity SUPPORT ME ⭐ --------------------------------------------------- Sign up on Patreon to get your donor role and early access to videos! https://patreon.com/mCoding Feeling generous but don't have a Patreon? Donate via PayPal! (No sign up needed.) https://www.paypal.com/donate/?hosted_button_id=VJY5SLZ8BJHEE Want to donate crypto? Check out the rest of my supported donations on my website! https://mcoding.io/donate Top patrons and donors: Jameson, Laura M, Dragos C, Vahnekie, Neel R, Matt R, Johan A, Casey G, Mark M, Mutual Information, Pi BE ACTIVE IN MY COMMUNITY 😄 --------------------------------------------------- Discord: https://discord.gg/Ye9yJtZQuN Github: https://github.com/mCodingLLC/ Reddit: https://www.reddit.com/r/mCoding/ Facebook: https://www.facebook.com/james.mcoding CHAPTERS --------------------------------------------------- 0:00 Intro 0:38 Timing 1k, 10k, 100k 1:30 Performance is relative 2:09 Big O Analysis 2:45 Amortized constant time 3:15 Putting it together