为何遍历单链表200次与1次的时间复杂度均表示为O(n)？

Great question—this is one of the most common "wait, that doesn't add up" moments when learning about time complexity, and it’s totally valid to ask! Let’s break this down clearly:

First, let’s remember what big O notation is actually for. It’s not meant to measure the exact runtime of an algorithm—it’s a tool to describe how the runtime scales as the input size (here, n, the number of linked list nodes) grows larger and larger. The key rule here is that big O ignores constant factors (like that 200 multiplier) because they become irrelevant as n gets extremely large.

Let’s use concrete numbers to see why this makes sense:

• If n = 100, 1 traversal takes 100 operations, 200 traversals take 20,000 operations. That’s a huge difference for small inputs.
• But if n = 1,000,000, 1 traversal takes 1M operations, 200 traversals take 200M operations. Now compare that to an O(n²) algorithm, which would take 1e12 operations for the same n. Suddenly, the 200x multiplier is tiny compared to the order of magnitude gap between linear (O(n)) and quadratic (O(n²)) growth.

Big O’s core purpose is to categorize algorithms by their scalability—how well they handle increasingly massive inputs. Both 1 traversal and 200 traversals scale linearly: double n, and the runtime roughly doubles (times 200, but still follows the same linear trend). That’s why they share the same O(n) classification.

Now, does that mean constant factors never matter? Absolutely not! In real-world engineering, when you’re working with specific input sizes or performance-critical code, constants are super important. A 200x slowdown can break an application. But big O is designed to cut through implementation noise (like how many times you loop, or how fast your CPU is) to focus on the fundamental efficiency of the algorithm itself.

To sum it up: big O answers the question "What happens when my input gets really, really big?"—and for that question, the difference between 1×n and 200×n is nothing compared to the gap between n and n², n log n, or 2ⁿ.

内容的提问来源于stack exchange，提问作者Umar