What is Big O notation?

Big O notation (or O-notation) is a way to describe the asymptotic behavior of a function, most often used for analyzing algorithm efficiency, i.e., how the runtime or memory usage of an algorithm scales with increasing input size.

Main aspects:

• Upper bound: O-notation describes the upper bound of growth, ignoring constants and lower order terms. It shows the worst-case performance.
• Asymptotic behavior: Focuses on the behavior as input size approaches infinity.
• Comparison of algorithms: Allows comparing algorithms regardless of hardware or programming language.

Examples of common complexity classes:

Notation	Name	Description	Example operation
O(1)	Constant time	Execution time does not depend on input size.	Accessing array element by index
O(log n)	Logarithmic	Execution time grows logarithmically with data size.	Binary search in sorted array
O(n)	Linear	Execution time proportional to data size.	Linear search in list
O(n log n)	Linearithmic	Grows proportionally to n * log n.	QuickSort (average), merge sort
O(n^2)	Quadratic	Grows proportionally to square of data size.	Bubble sort, nested loops
O(2^n)	Exponential	Grows exponentially.	Brute-force solutions for TSP

# Example O(1)
def get_first_element(arr):
    return arr[0] # Constant time regardless of arr size

# Example O(n)
def find_max(arr):
    max_val = arr[0]
    for element in arr: # Iterate over all elements
        if element > max_val:
            max_val = element
    return max_val

# Example O(n^2)
def print_pairs(arr):
    for i in arr: # First nested loop
        for j in arr: # Second nested loop
            print(i, j)

Choosing an algorithm favors the one with lower asymptotic complexity for large inputs, as it directly affects performance and scalability.