Where does the concept of time complexity O(n) come from and why is it preferable to O(n²)?

O(n) means that the algorithm's running time grows linearly with the increase in input size (n). This occurs when the algorithm processes each input element once or a constant number of times.

O(n²) means that the algorithm's running time grows quadratically with the increase in input size. This is typical for algorithms with nested iterations over data (for example, two nested loops, each iterating over n elements).

O(n) is preferable to O(n²) because, as the input size (n) increases, the execution time of an O(n) algorithm grows much slower than that of an O(n²) algorithm. For large n, the difference in execution time becomes very significant.

Example: If n = 1000: O(n) - execution time proportional to 1000 O(n²) - execution time proportional to 1000² = 1,000,000

# Example of an O(n) algorithm
def find_max(arr):
  """Finds the maximum element in a list."""
  max_val = arr[0] # O(1) - constant time
  for item in arr: # O(n) - loop over all n elements
    if item > max_val: # O(1)
      max_val = item # O(1)
  return max_val # O(1)
# Total complexity: O(1) + O(n) * (O(1) + O(1)) + O(1) = O(n)

# Example of an O(n²) algorithm
def bubble_sort(arr):
  """Bubble sort."""
  n = len(arr) # O(1)
  for i in range(n): # Outer loop - O(n)
    for j in range(0, n - i - 1): # Inner loop - O(n)
      if arr[j] > arr[j + 1]: # O(1)
        arr[j], arr[j + 1] = arr[j + 1], arr[j] # O(1)
# Total complexity: O(1) + O(n) * O(n) * (O(1) + O(1)) = O(n²)

Time complexity	Example of growth in execution time (arbitrary units)
O(n)	n
O(n²)	n * n