( O(n^2) ) Time Complexity explanation with a Simple Program

Introduction

Time complexity helps us understand how the running time of an algorithm grows with the size of the input. ( O(n^2) ) is a common time complexity that indicates the running time increases quadratically with the input size. This is often seen in algorithms that involve nested iterations.

In this blog post, we’ll explore what ( O(n^2) ) time complexity means, why it’s important, and how to identify it in your code using a simple example.

What is ( O(n^2) )?

The notation ( O(n^2) ) describes an algorithm whose performance grows quadratically with the size of the input. Here, n represents the size of the input. This means that if the input size doubles, the running time quadruples. ( O(n^2) ) is often seen in algorithms that use nested loops to compare or process each pair of elements in a dataset.

Example: Bubble Sort

Let’s look at an example to understand ( O(n^2) ) better.

Description

Bubble sort is a classic example of ( O(n^2) ) time complexity. It sorts an array by repeatedly stepping through the list, comparing adjacent pairs, and swapping them if they are in the wrong order. The process is repeated until the list is sorted.

Java Code Example

Here’s a simple Java program that implements bubble sort:

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;

        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap arr[j] and arr[j + 1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // If no two elements were swapped in the inner loop, then break
            if (!swapped) break;
        }
    }

    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(array);
        System.out.print("Sorted array: ");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

Explanation

1. Outer Loop: The outer loop iterates over the entire array, ensuring that the process continues until the array is sorted.

   for (int i = 0; i < n - 1; i++) {

2. Inner Loop: The inner loop compares adjacent elements and swaps them if they are in the wrong order.

   for (int j = 0; j < n - i - 1; j++) {
       if (arr[j] > arr[j + 1]) {
           // Swap elements
       }
   }

3. Swapping: Elements are swapped if they are out of order.

   int temp = arr[j];
   arr[j] = arr[j + 1];
   arr[j + 1] = temp;

The key is that for every element, the algorithm performs a linear scan to place it in its correct position, leading to quadratic behavior.

Time Complexity Analysis

Let’s analyze the time complexity step by step.

1. Outer Loop: The outer loop runs n - 1 times.

   for (int i = 0; i < n - 1; i++) {

2. Inner Loop: The inner loop runs up to n - i - 1 times for each iteration of the outer loop.

   for (int j = 0; j < n - i - 1; j++) {

Combining the Steps

The total number of comparisons is the sum of the series:

[ (n – 1) + (n – 2) + … + 1 ]

This series sums up to:

[ \frac{n(n – 1)}{2} ]

Which simplifies to:

[ O(n^2) ]

Why Is This Less Efficient?

In ( O(n^2) ), the time complexity grows quadratically as the input size increases. This means that even a small increase in the input size can significantly increase the execution time, making it less efficient for large datasets compared to linear or logarithmic time complexities.

Visual Aid

n comparisons on 1st pass
(n-1) comparisons on 2nd pass
...
1 comparison on last pass
--------------------------------
  Total: n(n-1)/2 = O(n^2)

Comparison with More Efficient Sorting Algorithms

To understand the difference, consider sorting algorithms with better time complexities like merge sort (( O(n \log n) )) or quicksort (average case ( O(n \log n) )). These algorithms perform better on large datasets compared to bubble sort due to their more efficient division and conquer strategies.

Here’s a quick comparison:

Algorithm	Best Time Complexity	Average Time Complexity	Worst Time Complexity
Bubble Sort	( O(n) )	( O(n^2) )	( O(n^2) )
Merge Sort	( O(n \log n) )	( O(n \log n) )	( O(n \log n) )
Quick Sort	( O(n \log n) )	( O(n \log n) )	( O(n^2) )

Summary

The time complexity of algorithms like bubble sort, which involve nested loops, is ( O(n^2) ). This means the execution time grows quadratically with the size of the input, making it less efficient for large datasets compared to algorithms with linear or logarithmic time complexities.

---

Conclusion

Understanding ( O(n^2) ) time complexity is crucial for recognizing algorithms that may not scale well with large inputs. By learning to identify these patterns, you can avoid writing code that becomes inefficient as the input size grows. Keep practicing with different examples to strengthen your grasp on time complexity.

---

Feel free to leave comments or questions below. Happy coding!