O(n²) – Quadratic Time Complexity

byMD Modasshar hussain -
0


O(n²) – Quadratic Time Complexity

After learning about O(n log n), let's move to another important type of Time Complexity called Quadratic Time Complexity, written as O(n²).

This is one of the most common time complexities that beginners encounter while learning programming and algorithms.

Many simple algorithms use O(n²) because they are easy to understand and implement. However, these algorithms become slow when the input size increases.

Let's understand why.

O(n²) – Quadratic Time Complexity


{tocify} $title={Table of Contents}


What is O(n²)?

O(n²) means the running time of an algorithm increases with the square of the input size.

In simple words, if the input size doubles, the number of operations becomes approximately four times larger.

If the input size becomes three times larger, the work becomes about nine times larger.

This rapid growth makes Quadratic algorithms inefficient for handling large datasets.

Simple Definition

Quadratic Time Complexity (O(n²)) means that for every input element, the algorithm performs another complete loop over all the elements.

Because of this, the total number of operations becomes:

n × n = n²

This is why it is called Quadratic Time Complexity.

Real-Life Example

Imagine you are organizing a classroom competition.

There are 10 students, and each student has to play a game with every other student.

Student 1 plays against all 10 students.

Student 2 also plays against all 10 students.

Student 3 repeats the same process.

This continues until every student has played with everyone.

If there are more students, the number of matches grows very quickly.

This is a perfect example of O(n²).

Why Does O(n²) Become Slow?

Suppose we compare every student with every other student.

StudentsComparisons
525
10100
10010,000
1,0001,000,000

Notice how quickly the number of operations increases.

This is why Quadratic algorithms are not suitable for processing millions of records.

Understanding O(n²) with Nested Loops

The easiest way to identify O(n²) is by looking for nested loops.

Consider this simple C++ program.

#include <iostream>
using namespace std;

int main()
{
    int n = 5;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cout << "(" << i << "," << j << ") ";
        }

        cout << endl;
    }

    return 0;
}

Output

(1,1) (1,2) (1,3) (1,4) (1,5)

(2,1) (2,2) (2,3) (2,4) (2,5)

(3,1) (3,2) (3,3) (3,4) (3,5)

(4,1) (4,2) (4,3) (4,4) (4,5)

(5,1) (5,2) (5,3) (5,4) (5,5)

The outer loop runs 5 times.

For every iteration of the outer loop, the inner loop also runs 5 times.

Total operations:

5 × 5 = 25

If n = 100, then:

100 × 100 = 10,000 operations

Therefore,

Time Complexity = O(n²)

Visual Representation

Imagine a table.

        1   2   3   4

1       ✔   ✔   ✔   ✔

2       ✔   ✔   ✔   ✔

3       ✔   ✔   ✔   ✔

4       ✔   ✔   ✔   ✔

Every row interacts with every column.

Rows = n

Columns = n

Total cells:

n × n = n²

This is exactly how Quadratic algorithms work.

Bubble Sort Example

One of the most famous algorithms with O(n²) complexity is Bubble Sort.

Bubble Sort repeatedly compares two adjacent elements and swaps them if they are in the wrong order.


Bubble Sort Example


C++ Program

#include <iostream>
using namespace std;

int main()
{
    int arr[] = {5, 2, 4, 1, 3};

    int n = 5;

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

    cout << "Sorted Array:" << endl;

    for(int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
}

Output

Sorted Array

1 2 3 4 5

Bubble Sort uses two loops.

The outer loop controls the number of passes.

The inner loop compares elements.

Since both loops depend on n, Bubble Sort has:

O(n²)

Another Real-Life Example

Suppose you have 100 photos on your phone.

You want to compare every photo with every other photo to find duplicate images.

Photo 1 is compared with all photos.

Photo 2 is compared with all photos.

Photo 3 repeats the same process.

This continues until every photo has been checked.

As the number of photos increases, the total comparisons grow rapidly.

This is another example of Quadratic Time Complexity.

O(n²) Growth Table

Input SizeNumber of Operations
10100
20400
502,500
10010,000
500250,000
1,0001,000,000

Notice how increasing the input size slightly causes the number of operations to increase dramatically.

O(n) vs O(n log n) vs O(n²)

Input SizeO(n)O(n log n)O(n²)
10010066410,000
1,0001,0009,9661,000,000
10,00010,000132,877100,000,000

As you can see, O(n²) becomes much slower than both O(n) and O(n log n) when the input size grows.

Where is O(n²) Used?

Although Quadratic algorithms are slower, they are still useful in some situations.

Common uses include:

  • Bubble Sort
  • Selection Sort
  • Insertion Sort (Worst Case)
  • Comparing every pair of elements
  • Duplicate detection using nested loops
  • Matrix operations
  • Pattern matching problems
  • Small datasets where simplicity is more important than speed

Advantages of O(n²)

  • Easy to understand.
  • Simple to implement.
  • Good for beginners learning algorithms.
  • Works well for small datasets.
  • Helpful for educational purposes.

Disadvantages of O(n²)

  • Very slow for large datasets.
  • Uses many unnecessary comparisons.
  • Not suitable for real-time applications.
  • Modern software usually avoids Quadratic algorithms when faster options are available.

Interview Tip

If you notice two nested loops, don't immediately assume the algorithm is O(n²).

Ask yourself:

  • Do both loops depend on n?
  • Does the inner loop run for every iteration of the outer loop?

If the answer is yes, then the Time Complexity is usually O(n²).

However, some nested loops run fewer times, so always analyze the code carefully instead of relying only on the number of loops.

Quick Revision

  • O(n²) is called Quadratic Time Complexity.
  • It usually appears when an algorithm contains two nested loops.
  • The running time grows as the square of the input size.
  • Bubble Sort and Selection Sort are common examples.
  • O(n²) works well for small datasets but becomes slow for large amounts of data.
  • Whenever possible, developers prefer O(n log n) algorithms because they perform much better on larger inputs.

🧩 Algorithm




Learn algorithms with examples and step-by-step explanations

📘 IT Tech Language




☁️ Cloud Computing
🧩 Algorithm
🤖 Artificial Intelligence (AI)
📊 Data Analyst


🧠 Machine Learning (ML)
🗄️ SQL
💠 C++ Programming


🐍 Python
🌐 Web Development
🚀 Tech to Know & Technology







Tags

You may like these posts

Post a Comment

Ask any query by comments

Previous Post Next Post