What is Big O notation?

Big O notation is a mathematical notation used to describe the asymptotic behavior of a function and its upper bound. In software development, it is used to evaluate the performance of algorithms in terms of time consumption (time complexity) and memory (space complexity) as the size of input data grows. It describes the worst-case scenario.

The most common classes of time complexity:

• O(1): Constant time. Execution time does not depend on the size of input data.
• O(log n): Logarithmic time. Execution time grows slowly as the size of input data increases (e.g., binary search).
• O(n): Linear time. Execution time is directly proportional to the size of input data (e.g., simple iteration).
• O(n log n): Linearithmic time. Often found in efficient sorting algorithms (e.g., quicksort, merge sort).
• O(n^2): Quadratic time. Execution time grows proportionally to the square of the input size (e.g., bubble sort, selection sort).
• O(2^n): Exponential time. Execution time grows very rapidly with the increase in input size. Often found in brute-force problems.

Code examples and their time complexity:

// O(1)
int firstElement = array[0];

// O(n)
for (int i = 0; i < array.length; i++) {
    // some operation
}

// O(n^2)
for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array.length; j++) {
        // some operation
    }
}

Big O notation focuses on the dominant term in the expression and ignores constants and less significant terms, as their contribution becomes negligible with large input data. For example, an algorithm with complexity O(2n^2 + 5n + 10) is considered O(n^2).

Understanding Big O is important for choosing the most efficient algorithms and data structures in development.