What is computational complexity and why is it important in programming?

Computational complexity is a measure of the resources required to execute an algorithm. Most often, it evaluates execution time and the amount of memory used.

Importance in programming:

1. Performance: Allows predicting how an algorithm will behave as input size increases and choosing the most efficient among several options.
2. Scalability: Helps understand whether a solution can handle increased load, which is critical for large systems.
3. Optimization: Identifies "bottlenecks" in code for subsequent optimization.
4. Algorithm selection: Enables comparison of algorithms based on their theoretical efficiency before practical testing.

It is usually evaluated using "Big O" notation, which describes the asymptotic behavior of an algorithm with large input data.

Examples of notations and their meanings:

Notation	Complexity	Description
O(1)	Constant	Time does not depend on input size
O(log n)	Logarithmic	Time grows slowly with increasing data
O(n)	Linear	Time grows proportionally with data
O(n log n)	Quasilinear	Typical for efficient sorts
O(n²)	Quadratic	Time increases rapidly with data size
O(2ⁿ)	Exponential	Time grows very fast, unsuitable for large data

# Example: Linear complexity O(n)
def find_max(arr):
    # Iterate through each element of the array once
    if not arr:
        return None
    max_val = arr[0]
    for x in arr:
        if x > max_val:
            max_val = x
    return max_val

# Example: Quadratic complexity O(n^2)
def bubble_sort(arr):
    n = len(arr)
    # In the worst case, for each element, iterate through remaining n-i elements
    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]
    return arr

# Example: Constant complexity O(1)
def get_first_element(arr):
    # Getting the first element takes the same time regardless of array size
    if arr:
        return arr[0]
    return None