Big O Notation: Key Concepts

2.1 Defining Big O Notation.

Big O notation is a mathematical notation used to describe the upper bound of an algorithm's runtime or resource consumption based on the size of its input. It helps to determine how well an algorithm scales and how its performance changes as the data volume increases.

Big O notation focuses on the most significant aspects of an algorithm, ignoring constants and less significant terms, allowing for a focus on the long-term behavior of the algorithm.

Main notations:

O(1) — Constant complexity:

• The runtime of the algorithm doesn't depend on the size of the input data.
• Example: accessing an array element by index.

O(n) — Linear complexity:

• The runtime of the algorithm is linearly dependent on the size of the input data.
• Example: simple iteration over all elements of an array.

O(log n) — Logarithmic complexity:

• The runtime of the algorithm grows logarithmically with an increase in the input data size.
• Example: binary search in a sorted array.

O(n^2) — Quadratic complexity:

• The runtime of the algorithm is quadratically dependent on the size of the input data.
• Example: bubble sort, insertion sort.

O(2^n) — Exponential complexity:

• The runtime of the algorithm grows exponentially with the size of the input data.
• Example: solving the knapsack problem using brute force.

2.2 Interpreting Big O Notation.

How to interpret and use Big O notation?

Ignoring constants and less significant terms:

Big O describes the growth order of a function, ignoring constants and less significant terms. For example, O(2n) and O(3n) are interpreted as O(n).

Comparing algorithms:

Big O allows comparing algorithms based on their asymptotic efficiency. For example, an algorithm with O(n log n) is more efficient than one with O(n^2) for very large data volumes.

Worst-case analysis:

Big O is typically used for analyzing the worst-case runtime of an algorithm, which allows estimating its maximum complexity.

Ignorance of constants.

Ignoring constants and less significant terms

Example 1:

Consider two functions:

• f(n) = 3n + 2
• g(n) = 5n + 1

Both functions have linear complexity because the dominant term in each function is n. Hence, both functions are interpreted as O(n), despite differences in coefficients and additional terms.

Example 2:

Consider two functions:

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

Both functions have quadratic complexity because the dominant term is n^2. Both expressions are interpreted as O(n^2), despite differences in other terms and coefficients.

2.3 Comparing Algorithms

1. Comparing algorithms on very large data volumes

Example 1:

• Algorithm A has a time complexity of O(n^2).
• Algorithm B has a time complexity of O(n log n).

For small values of n, algorithm A might run faster due to smaller constants, but for large values of n, algorithm B will be significantly faster, because its growth is logarithmic, not quadratic.

Example 2:

• Algorithm X has a time complexity of O(n).
• Algorithm Y has a time complexity of O(1).

Algorithm Y will always be faster, regardless of the size of n, because O(1) means that the runtime of the algorithm does not depend on the size of the input data.

2. Worst-case analysis

Example 1:

Bubble sort has a time complexity of O(n^2) in the worst case when the array is sorted in reverse order. This means that for each element in the array a comparison and possibly a swap is needed with every other element.

Example 2:

Binary search has a time complexity of O(log n) in the worst case. This means that even in the worst case, the number of steps needed to find an element will be logarithmic relative to the size of the array, which is very efficient.

3. Impact on performance and scalability

Example 1:

If we have two algorithms for processing data, one with a time complexity of O(n^2), and another with O(n log n), and we increase the data size from 1000 elements to 10,000 elements, the performance difference will be significantly noticeable.

• The algorithm with O(n^2) will perform approximately 100,000,000 operations for 10,000 elements.
• The algorithm with O(n log n) will perform about 40,000 operations for 10,000 elements.

Example 2:

Consider an algorithm that operates in O(2^n). If we increase the input data size from 10 to 20 elements, the number of operations increases exponentially.

• For n = 10: 2^10 = 1024 operations.
• For n = 20: 2^20 = 1,048,576 operations.

This demonstrates how quickly exponential complexity becomes impractical for large values of n.