Quadratic Time Complexity

Quadratic time complexity means that the time taken by an algorithm is proportional to the square of the size of the input (( n^2 )). This type of time complexity is common in algorithms that involve nested loops, where each element is compared or processed with every other element.

An algorithm with O(n²) time complexity becomes significantly slower as the input size increases. For example, doubling the input size will quadruple the number of operations.

Example: Bubble Sort

Suppose you have the following unsorted list of numbers:

[4, 3, 5, 2, 1]

You want to sort this list in ascending order using Bubble Sort, which has a time complexity of O(n²).

How Bubble Sort Works

1. Step 1: Start at the beginning of the list and compare each pair of adjacent elements.
   • Compare 4 and 3 → Swap them: [3, 4, 5, 2, 1]
   • Compare 4 and 5 → No swap needed
   • Compare 5 and 2 → Swap them: [3, 4, 2, 5, 1]
   • Compare 5 and 1 → Swap them: [3, 4, 2, 1, 5]
2. Step 2: Repeat the process for the remaining elements.
   • After first pass: Largest element (5) is in the correct position.
   • Repeat the process for the rest of the list: [3, 4, 2, 1]
3. Step 3: Continue until the entire list is sorted.
   • Final sorted list: [1, 2, 3, 4, 5]

In the worst case, Bubble Sort requires ( n \times (n-1) / 2 ) comparisons, which simplifies to O(n²).

Why is Bubble Sort O(n²)?

• The algorithm uses nested loops:
  • The outer loop runs ( n ) times.
  • The inner loop runs up to ( n-1 ) times for each iteration of the outer loop.
• Therefore, the total number of operations is approximately ( n \times n ), resulting in O(n²) complexity.

Real-Life Analogy

Imagine you have a list of 10 students standing in a line in random height order, and you want to arrange them from shortest to tallest. To do this:

1. You start by comparing the first two students and swap them if needed.
2. Then, move to the next pair of students and repeat the comparison.
3. Once you reach the end of the line, you start over from the beginning.
4. You continue this process until no more swaps are needed.

As the number of students increases, the number of comparisons and swaps grows rapidly, making this process take a lot longer. This is similar to how O(n²) algorithms work.