Why Time Complexity Matters?¶

Imagine you have a task: finding a specific name in a phonebook. There are two methods:

• Method 1: Start from the beginning, flipping through pages one by one until you find the target name. If the name is on the last page, you’ll need to flip many pages.
• Method 2: Directly use the directory index to quickly locate the name.

Clearly, Method 2 is faster, especially when the phonebook is large. This is what we call the “efficiency” problem—the difference in “speed” between different algorithms.

In programming, every algorithm we write (such as search or sorting) has an execution time. However, directly calculating “how many seconds” it takes is impractical (because computer performance, compilers, etc., affect the result). Thus, we use time complexity to abstractly describe the “efficiency trend” of an algorithm.

What is Time Complexity O(n)?¶

Time complexity measures how the execution time of an algorithm grows as the input data size increases. It is represented using the Big O Notation (e.g., O(n)), focusing on how the number of operations grows as the input size n increases.

• O(n) denotes “linear time complexity.” Here, n typically refers to the size of the input data (e.g., array length, number of elements).
• Linear Relationship: As the input size n increases, the number of operations the algorithm needs increases proportionally to n. For example:
• If n=5 (5 elements), the algorithm needs 5 operations;
• If n=10, it needs 10 operations;
• If n=1000, it needs 1000 operations.

Understanding O(n) with Examples¶

Example 1: Traverse an Array to Find a Target Element¶

Suppose you want to find a “target number” in an array. The simplest approach is to check each element one by one:

def find_target(arr, target):
    for num in arr:  # Loops n times (n is the array length)
        if num == target:
            return True
    return False

• Number of operations: In the worst case, you need to check all elements of the array (e.g., the target does not exist or is at the last position). If the array has n elements, you need n comparison operations.
• Time complexity: O(n), because the number of operations is proportional to n (as n increases, the number of operations increases linearly).

Example 2: Print All Elements¶

Another example: Print all elements in an array:

def print_all(arr):
    for num in arr:  # Loops n times
        print(num)

• Number of operations: Again, you need n print operations (one for each element).
• Time complexity: O(n).

Why Use Big O Notation?¶

If you directly say “this algorithm takes n operations,” someone might mistakenly think that when n=1000, it takes exactly 1000 operations. However, in reality, when n increases from 1000 to 10000, the number of operations increases from 1000 to 10000—this is the meaning of “linear growth.”

The core of Big O notation is to ignore constants and lower-order terms, focusing only on “how the number of operations grows as the input size n increases.” For example:
- O(n) means “number of operations ≈ n”;
- O(2n + 5) is actually equivalent to O(n) (since 2 and 5 are constants, their impact is negligible as n grows);
- O(n + 1000) is also equivalent to O(n).

Comparing O(n) with Other Complexities¶

Here are common time complexities (from most efficient to least efficient):

As you can see: O(n) is more efficient than O(n²) but less efficient than O(1) or O(log n).

Key Summary¶

• O(n) represents linear time complexity, meaning the algorithm’s execution time grows proportionally to the input size n.
• n typically refers to the size of the input data (e.g., array length, number of list elements).
• Big O Notation focuses only on the “trend” of growth, ignoring constants and specific time values.
• Why it matters: Understanding O(n) is fundamental to data structures and algorithms. It helps you write more efficient code and avoid “brute-force” solutions that lead to timeouts, especially when the data scale is large!

Next time you encounter an algorithm problem, consider asking, “What is the time complexity of this algorithm?”—especially when the data size is large, the difference between O(n) and O(n²) becomes extremely significant!