You can write a function that works, but how do you know if it's good? Running code and timing it with a stopwatch isn't a reliable way to measure performance. The result changes based on your computer's hardware, its current workload, and the specific data you test with. We need a consistent way to talk about an algorithm's efficiency that's independent of the machine it runs on.

This is where Big O notation comes in. It doesn't measure time in seconds; it measures the rate of growth of the time or space an algorithm requires as its input size ($n$) increases. It describes the worst-case scenario, giving us an upper bound on performance.

For example, accessing an element in a Python list by its index (e.g., my_list[5]) is an $O(1)$ operation. It takes the same amount of time whether the list has 10 elements or 10 million. In contrast, checking if an element exists in an unsorted list requires looking at each item one by one, making it an $O(n)$ operation.

Python's list is not just a simple list; it's a dynamic array. This means it can grow and shrink as needed. But how does it do this efficiently? When you create a list, Python allocates a certain amount of memory for it, enough to hold a few elements. When you append items and that allocated space runs out, Python doesn't just add one more slot. That would be incredibly inefficient.

Instead, it allocates a completely new, larger block of memory, copies all the old elements over to the new location, and then adds the new element. The old memory block is then freed. This resizing process is an $O(n)$ operation because it has to touch every existing element. So, if appending is sometimes $O(n)$, why do we say it's fast?

The key is that Python over-allocates. It might double the allocated memory each time it resizes. This means the expensive $O(n)$ copy operation happens less and less frequently as the list grows. The cost of these occasional resizes, when averaged out over many append operations, is small. This concept is called amortized time complexity—we're spreading the cost of the expensive operation over all the cheap ones.

However, inserting an element at the beginning of a list (e.g., my_list.insert(0, 'new_item')) is always $O(n)$. To make room at the front, every single existing element must be shifted one position to the right. There's no amortization to save us here.

This brings us to the fundamental difference between Python's two main sequence types: lists are mutable (changeable), and tuples are immutable (unchangeable). This isn't just a minor detail; it has significant performance and architectural implications.

Because a tuple's size and contents are fixed, Python doesn't need to allocate extra memory for it. It knows exactly how much space is required from the start. This makes tuples slightly more memory-efficient.

More importantly, an object's immutability makes it hashable—meaning its value can be used to generate a unique, consistent number (its hash). Dictionaries use this hash to quickly look up keys. Since a list's contents can change, its hash would also change, making it unreliable as a dictionary key. Tuples, being immutable, are perfectly suited for this role.

Finally, let's consider slicing. When you slice a list or a tuple (e.g., new_list = old_list[1:5]), you are creating a new copy of that segment of data. The time it takes to do this is proportional to the size of the slice you are creating. If you slice $k$ elements, the operation is $O(k)$. It's not a free operation that just creates a 'view' into the original data; it allocates new memory and copies the elements over.

Ready to test your understanding?

Understanding these performance characteristics is the first step toward writing professional, scalable code. It allows you to make informed decisions about which data structure is the right tool for the job.