Grokking Algorithm Complexity and Big-O
Ask Author
Back to course home

0% completed

Vote For New Content
Quadratic Time: O(n²)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Quadratic Time Complexity O(n^2) describes algorithms where the runtime grows proportionally to the square of the input size. In other words, if the input size doubles, the time taken by the algorithm quadruples. This complexity commonly appears in algorithms with nested loops, where each loop iterates over the input.

Image

Key Characteristics

In an algorithm with O(n^2) time complexity:

  • The runtime increases quadratically as the input size grows.
  • This complexity is often seen in algorithms where each element is compared with every other element, such as certain sorting algorithms.

Code Example

Here’s an example of an O(n^2) algorithm. This function checks for duplicate elements in a list by comparing each element with every other element:

Python3
Python3
. . . .
  • Explanation: In the has_duplicates method, the outer loop iterates through each element, while the inner loop checks every other element after it. For each element in arr, we compare it with every subsequent element.
Image
  • Why O(n^2)? If arr has n elements, the outer loop runs n times, and for each iteration of the outer loop, the inner loop runs up to n-1 times. This results in roughly n \times (n-1) / 2 comparisons, giving a time complexity of O(n^2).

Examples of O(n^2) operations

  • Bubble Sort or Selection Sort: Sorting algorithms like bubble sort compare each element with others, making them O(n^2) in time complexity.
  • Checking for Duplicate Pairs: In a scenario where you need to check all pairs of items in a list, such as finding all pairs with a specific difference, the process takes quadratic time.
  • Distance Calculation Between Points: If you’re calculating distances between each pair of points in a 2D space, the time taken grows quadratically with the number of points.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible