How to evaluate the complexity of an algorithm and…

Algorithm complexity assessment is often carried out by analyzing the number of basic operations performed by the algorithm depending on the size of the input data (n). Asymptotic complexity describes the behavior of the algorithm as n approaches infinity, ignoring constant factors and lower-order terms. To determine asymptotics, the "Big O" notation (O-notation) is used.

Main steps:

Identify the basic operation: Determine the operation that is performed most frequently and whose count is proportional to the total execution time of the algorithm. This could be comparison, assignment, arithmetic operation, etc.
Count the number of basic operations: Express the number of basic operations as a function of the input size n.
Determine the asymptotic complexity: From the obtained function, keep only the highest order term and discard constant multipliers. This will be the asymptotic complexity of the algorithm in O-notation.

Common classes of asymptotic complexity:

O(1) - constant complexity (independent of n)
O(log n) - logarithmic complexity
O(n) - linear complexity
O(n log n) - linear-logarithmic complexity
O(n²) - quadratic complexity
O(2ⁿ) - exponential complexity

Examples:

Searching for an element in an unsorted array: In the worst case, all n elements need to be examined. Basic operation: comparison. Number of operations: n. Asymptotics: O(n).
Searching for an element in a sorted array (binary search): At each step, the search area size is halved. Basic operation: comparison. Number of operations: log₂ n. Asymptotics: O(log n).
Bubble sort: Requires n-1 passes, each with up to n-1 comparisons. Basic operation: comparison and swap. Number of operations: approximately n²/2. Asymptotics: O(n²).

When analyzing, the worst, average, and best cases of algorithm execution are also considered, although the worst case is most often evaluated.

# Example: counting the number of operations in a simple loop
def simple_loop(n):
  count = 0 # 1 operation
  for i in range(n): # Loop runs n times
    count += 1 # 1 operation inside the loop
  return count

# Total number of operations: 1 (initialization) + n * 1 (operations in loop) = 1 + n
# Asymptotics: O(n)

# Example: nested loops
def nested_loops(n):
  count = 0 # 1 operation
  for i in range(n): # Outer loop n times
    for j in range(n): # Inner loop n times
      count += 1 # 1 operation inside inner loop
  return count

# Total number of operations: 1 (initialization) + n * (n * 1) = 1 + n²
# Asymptotics: O(n²)

How to evaluate the complexity of an algorithm and determine its asymptotics?