Can you explain what the notation O(n) means in algorithm analysis?

The notation O(n) in algorithm analysis is called "asymptotic complexity" or "runtime complexity" of an algorithm. It shows how the execution time of the algorithm grows depending on the size of the input data n. In the case of O(n), the execution time increases linearly with the growth of n.

For example, if you have an algorithm that passes through a list of n elements once, its complexity will be O(n). This means that if the number of elements doubles, the running time will roughly double as well.

Example in Python:

def sum_list(lst):
    total = 0
    for item in lst:
        total += item
    return total

Here, the function passes through each element of the list once, so its complexity is O(n).