Where does the notation O(n) come from and why is it better than O(n²)?

O(n) notation (or Big O notation) describes the asymptotic behavior of a function that characterizes the time or memory used by an algorithm as the size of input data (n) increases.

Mathematically, f(n) = O(g(n)) means that there exist positive constants c and n₀ such that for all n ≥ n₀, f(n) ≤ c * g(n). g(n) here represents the dominant term in the expression for f(n), ignoring constants and lower-order terms.

For example, an algorithm performing 3n + 5 operations has a complexity of O(n), since for large n, the 3n term dominates, and the constant 5 becomes insignificant. We ignore the constant 3 and 5, leaving the n term.

An O(n) complexity means that the execution time (or memory used) grows linearly with the increase in input data size. If the input data doubles, the execution time roughly doubles.

An O(n²) complexity means that the execution time grows quadratically with the increase in input data size. If the input data doubles, the execution time increases by approximately four times.

O(n) is better than O(n²) because as n grows, the function n grows much slower than n². This means that algorithms with linear complexity scale much better than quadratic ones on large data volumes.

Let's consider an example:

n	O(n) = n	O(n²) = n²
1	1	1
10	10	100
100	100	10000
1000	1000	1000000

As seen from the table, the performance difference between O(n) and O(n²) becomes noticeable as n increases, and this difference grows rapidly.

Example of an O(n) algorithm:

# Simple loop that runs once over all list elements
def linear_search(arr, target):
  for item in arr:
    if item == target:
      return True
  return False

Example of an O(n²) algorithm:

# Nested loops to compare all pairs of list elements
def bubble_sort(arr):
  n = len(arr)
  for i in range(n):
    for j in range(0, n - i - 1):
      if arr[j] > arr[j + 1]:
        arr[j], arr[j + 1] = arr[j + 1], arr[j]

When choosing an algorithm, preference is given to the one with lower asymptotic complexity for large input data, as this directly affects performance and scalability of the solution.