📈 Big O Notation and Algorithm Analysis Report

I. Understanding Big O Notation

Big O notation is a mathematical notation used in computer science to describe the limiting behavior of a function when the argument tends toward a particular value or infinity. In the context of algorithms, it expresses the worst-case time complexity or space complexity of an algorithm as the size of the input data ($n$) grows. This notation measures an algorithm's efficiency by quantifying how the running time or memory usage grows relative to the size of the input ($n$). It focuses on the highest-order term in the complexity function, ignoring coefficients and lower-order terms, as these factors become negligible for very large $n$.

Common Time Complexities

Notation	Name	Description (Worst Case)	Example Algorithm
$\mathcal{O}(1)$	Constant Time	Execution time remains the same regardless of the input size.	Accessing an array element by index.
$\mathcal{O}(\log n)$	Logarithmic Time	Execution time grows logarithmically with input size.	Binary Search.
$\mathcal{O}(n)$	Linear Time	Execution time is directly proportional to the input size.	Linear Search.
$\mathcal{O}(n \log n)$	Linearithmic Time	Time grows proportionally to $n$ multiplied by $\log n$.	Efficient sorting algorithms (Merge Sort, Quick Sort).
$\mathcal{O}(n^2)$	Quadratic Time	Execution time grows quadratically with the input size.	Simple sorting algorithms (Bubble, Insertion, Selection Sort).
$\mathcal{O}(2^n)$	Exponential Time	Execution time doubles for every additional element.	Brute-force solutions to NP-hard problems.

---

II. Analysis of Sorting Algorithms ($\mathcal{O}(n^2)$ Family)

The following table details the complexity analysis for the simple comparison-based sorting algorithms (Selection, Insertion, and Bubble Sort):

Algorithm	Best-Case Time Complexity	Average-Case Time Complexity	Worst-Case Time Complexity (Big O)
Selection Sort	$\mathcal{O}(n^2)$	$\mathcal{O}(n^2)$	$\mathcal{O}(n^2)$
Insertion Sort	$\mathcal{O}(n)$ (Already Sorted)	$\mathcal{O}(n^2)$	$\mathcal{O}(n^2)$
Bubble Sort	$\mathcal{O}(n)$ (Optimized/Already Sorted)	$\mathcal{O}(n^2)$	$\mathcal{O}(n^2)$

Detailed Rationale for $\mathcal{O}(n^2)$

All three algorithms exhibit quadratic time complexity in the worst and average cases because their implementation relies on nested loops over the dataset of size $n$, where the total number of operations grows proportionally to $n \times n$.

• Selection Sort: The process involves an outer loop running $\approx n$ times and an inner loop running $\approx n$ times to find the minimum element in the unsorted remainder.
• Insertion Sort: In the worst case (reverse sorted array), the outer loop runs $\approx n$ times, and the inner loop (shifts) may run up to $n$ times for each outer iteration.
• Bubble Sort: The algorithm requires $n-1$ passes (outer loop), and each pass performs up to $n-1$ comparisons (inner loop).

---

III. Conclusion

The $\mathcal{O}(n^2)$ complexity of these simple sorting algorithms highlights their limitation: their performance degrades rapidly as the input size ($n$) increases. While they are useful for educational purposes and small datasets, for large-scale operations, highly efficient algorithms with $\mathcal{O}(n \log n)$ complexity are required for better scalability and optimal performance.