Last Updated : 02 Apr, 2024
Improve
Prerequisite:
- Asymptotic Notation and Analysis
- Analysis of Algorithms | Big-O analysis
In this article, we’re going to explore into the concept of Big O(N^2) complexity, a crucial metric in algorithm analysis. Understanding what O(N^2) signifies is crucial for evaluating the efficiency of algorithms, especially those involving nested loops. We explore the implications of quadratic growth in time and space requirements, offering insights into optimization strategies and the impact on algorithmic performance.
Table of Content
- What is Time Complexity?
- What Does Big O(N2) Complexity Mean?
- What is O(N2) Time Complexity?
- Relationship Between Input Size and Algorithmic Time Complexity
- What is Space Complexity
- What is O(N2) Space Complexity?
- Relationship Between Input Size and Algorithmic Space Complexity
What is Time Complexity?
The Time complexity of an algorithm can be defined as a measure of the amount of time taken to run an algorithm as a function of the size of the input. In simple words, it tells about the growth of time taken as a function of input data.
Time complexity is categorized in 3 types:
- Best-Case Time Complexity: The minimum amount of time required by an algorithm to run, based on the given most suitable input is known as best-case complexity. It is denoted by the sign Big Omega (Ω).
- Average Case Complexity: The average amount of time required by an algorithm to run, taking into consideration all the possible inputs is known as average-case complexity. It is denoted by the sign Big Theta (Θ).
- Worst Case Complexity: The maximum amount of time required by an algorithm to run, taking into consideration possible worst case is known as worst-case complexity. It is denoted by the sign Big O(O).
While measuring the time complexity of any algorithm worst case complexity is taken into consideration as while designing a system we should consider the worst scenario. So, whenever someone say what is time complexity of algorithm they refer to worst-case complexity.
Now as we know what is time complexity, We will discuss about various time complexities:
What Does Big O(N2) Complexity Mean?
It is also known as Quadratic Time complexity. In this type the running time of algorithm grows as square function of input size. This can cause very large time for large inputs. Here, the notation ‘O’ in O(N2) represents its worst cases complexity.
What is O(N2) Time Complexity?
The O(N^2) time complexity means that the running time of an algorithm grows quadratically with the size of the input. It often involves nested loops, where each element in the input is compared with every other element.
Below are some programs having O(N2) time complexity for better understanding.
Example 1: Program to print 2D matrix
#include <bits/stdc++.h>using namespace std;// Function to print N*N 2D matrixvoid printMatrix(vector<vector<int> > matrix, int N){ for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { // Print each cell cout << matrix[i][j] << " "; } // Move to the next line after printing each row cout << endl; }}// Driver codeint main(){ // Define the size of the matrix (N*N) const int N = 3; // Create a 2D vector (matrix) vector<vector<int> > exampleMatrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; // Print the matrix using the printMatrix function cout << "Matrix:" << endl; printMatrix(exampleMatrix, N); // The matrix is automatically deallocated when it goes // out of scope return 0;}
import java.io.*;import java.util.Arrays;public class GFG { // Function to print N*N 2D matrix static void printMatrix(int[][] matrix, int N) { for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { // Print each cell System.out.print(matrix[i][j] + " "); } // Move to the next line after printing each row System.out.println(); } } // Driver code public static void main(String[] args) { final int N = 3; // Create a 2D array (matrix) int[][] exampleMatrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; // Print the matrix using the printMatrix function System.out.println("Matrix:"); printMatrix(exampleMatrix, N); }}
using System;class Program{ // Function to print N*N 2D matrix static void PrintMatrix(int[,] matrix, int N) { for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { // Print each cell Console.Write(matrix[i, j] + " "); } // Move to the next line after printing each row Console.WriteLine(); } } // Driver code static void Main() { // Define the size of the matrix (N*N) const int N = 3; // Create a 2D array (matrix) int[,] exampleMatrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; // Print the matrix using the PrintMatrix function Console.WriteLine("Matrix:"); PrintMatrix(exampleMatrix, N); // The matrix is automatically deallocated when it goes // out of scope }}
// Function to print N*N 2D matrixfunction printMatrix(matrix, N) { for (let i = 0; i < N; ++i) { for (let j = 0; j < N; ++j) { // Print each cell process.stdout.write(matrix[i][j] + " "); } // Move to the next line after printing each row console.log(); }}// Driver codefunction main() { // Define the size of the matrix (N*N) const N = 3; // Create a 2D array (matrix) const exampleMatrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]; // Print the matrix using the printMatrix function console.log("Matrix:"); printMatrix(exampleMatrix, N); // The matrix is automatically deallocated when it goes // out of scope}// Call the main functionmain();
# Python Implementationdef print_matrix(matrix): for row in matrix: for elem in row: # Print each cell with space separation print(elem, end=" ") # Move to the next line after printing each row print()if __name__ == "__main__": # Define the size of the matrix (N*N) N = 3 # Create a 2D list (matrix) example_matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] # Print the matrix using the print_matrix function print("Matrix:") print_matrix(example_matrix)# This code is contributed by Sakshi
Output
Matrix:1 2 3 4 5 6 7 8 9
Let’s break down the printMatrix() function to understand its time complexity:
- The outer loop (for loop with variable i) runs N times, iterating over each row of the matrix.
- The inner loop (for loop with variable j) also runs N times for each iteration of the outer loop, iterating over each element in the current row.
- Inside the inner loop, there is a constant amount of work being done for each iteration, which involves printing the value of the matrix cell at indices i and j.
The total number of print operations is N * N, where N is the size of the matrix (assuming it’s a square matrix with N rows and N columns). Therefore, the time complexity is proportional to the square of the input size, resulting in O(N2) time complexity.
Example 2: Program to prints all pairs of elements in an array:
#include <bits/stdc++.h>using namespace std;// Function to print all pairs of elements in an arrayvoid printAllPairs(int arr[], int N){ for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { cout << "(" << arr[i] << ", " << arr[j] << ") "; } }}// Driver codeint main(){ // Define the size of the array const int N = 3; // Create an array int exampleArray[N] = { 1, 2, 3 }; // Print all pairs using the printAllPairs function cout << "All pairs:" << std::endl; printAllPairs(exampleArray, N); return 0;}
// Java program for the above approachimport java.util.*;public class GFG { // Function to print all pairs of elements in an array public static void printAllPairs(int[] arr, int N) { for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { System.out.print("(" + arr[i] + ", " + arr[j] + ") "); } } } // Driver code public static void main(String[] args) { // Define the size of the array final int N = 3; // Create an array int[] exampleArray = { 1, 2, 3 }; // Print all pairs using the printAllPairs function System.out.println("All pairs:"); printAllPairs(exampleArray, N); }}// This code is contributed by Susobhan Akhuli
using System;class Program{ // Function to print all pairs of elements in an array static void PrintAllPairs(int[] arr, int N) { for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { Console.Write($"({arr[i]}, {arr[j]}) "); } } } // Driver code static void Main() { // Define the size of the array const int N = 3; // Create an array int[] exampleArray = { 1, 2, 3 }; // Print all pairs using the PrintAllPairs function Console.WriteLine("All pairs:"); PrintAllPairs(exampleArray, N); }}
// Function to print all pairs of elements in an arrayfunction printAllPairs(arr) { let pairs = ""; for (let i = 0; i < arr.length; ++i) { for (let j = 0; j < arr.length; ++j) { pairs += "(" + arr[i] + ", " + arr[j] + ") "; } } console.log(pairs);}// Driver codefunction main() { // Define the size of the array const N = 3; // Create an array const exampleArray = [1, 2, 3]; // Print all pairs using the printAllPairs function console.log("All pairs:"); printAllPairs(exampleArray);}// Invoke the main functionmain();
# Function to print all pairs of elements in an arraydef print_all_pairs(arr): # Traverse the array for i in range(len(arr)): for j in range(len(arr)): # Print each pair of elements print("(", arr[i], ",", arr[j], ")", end=" ")# Driver codeif __name__ == "__main__": # Define the array example_array = [1, 2, 3] # Print all pairs using the print_all_pairs function print("All pairs:") print_all_pairs(example_array)
Output
All pairs:(1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1) (3, 2) (3, 3)
Let’s break down the printAllPairs() function to understand its time complexity:
- The outer loop runs N times, where N is the size of the array.
- The inner loop also runs N times for each iteration of the outer loop.
As a result, for each element at index i in the array, the inner loop runs N times. Since this process is repeated for all elements in the array due to the outer loop, the total number of iterations becomes N * N, leading to a time complexity of O(N^2).
Relationship Between Input Size and Algorithmic Time Complexity:
Suppose the size of input is N and the time required for algorithm to process this input is X then the time will vary with size of input as given in following table:
Size of Input | Time Required |
|---|---|
N | X |
2N | 4X |
3N | 9X |
4N | 16X |
It can be represented as Time required = (size of input)2 * X
Although for small inputs it appears like it doesn’t impact on large scale but for bigger input it can heavily impact on performance of algorithm as the time increases as function of square of size of input.
What is Space Complexity:
Space complexity refers to the amount of memory an algorithm requires relative to its input size. It quantifies how the memory usage of an algorithm scales. Lower space complexity indicates better memory efficiency.
What is O(N2) Space Complexity?
The O(N2) space complexity means that the memory usage of an algorithm grows quadratically with the size of the input. It is often associated with algorithms that use a two-dimensional data structure, resulting in a space requirement proportional to the square of the input size.
Example: Program to generate an NxN matrix
#include <bits/stdc++.h>using namespace std;// Function to generate an NxN matrixvector<vector<int> > generateMatrix(int n){ vector<vector<int> > matrix(n, vector<int>(n, 0)); int value = 1; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { matrix[i][j] = value; value++; } } return matrix;}// Driver codeint main(){ // Specify the size of the matrix (N x N) int N = 3; // Generate the matrix using the generateMatrix function vector<vector<int> > exampleMatrix = generateMatrix(N); // Print the generated matrix for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { cout << exampleMatrix[i][j] << " "; } cout << endl; } return 0;}
// Java program for the above approachimport java.util.*;public class GFG { // Function to generate an NxN matrix static int[][] generateMatrix(int n) { int[][] matrix = new int[n][n]; int value = 1; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { matrix[i][j] = value; value++; } } return matrix; } // Driver code public static void main(String[] args) { // Specify the size of the matrix (N x N) int N = 3; // Generate the matrix using the generateMatrix // function int[][] exampleMatrix = generateMatrix(N); // Print the generated matrix for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { System.out.print(exampleMatrix[i][j] + " "); } System.out.println(); } }}// This code is contributed by Susobhan Akhuli
// C# program for the above approachusing System;public class GFG { // Function to generate an NxN matrix static int[][] GenerateMatrix(int n) { int[][] matrix = new int[n][]; for (int i = 0; i < n; i++) { matrix[i] = new int[n]; for (int j = 0; j < n; j++) { matrix[i][j] = i * n + j + 1; } } return matrix; } // Driver code static void Main(string[] args) { // Specify the size of the matrix (N x N) int N = 3; // Generate the matrix using the GenerateMatrix // function int[][] exampleMatrix = GenerateMatrix(N); // Print the generated matrix for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { Console.Write(exampleMatrix[i][j] + " "); } Console.WriteLine(); } }}// This code is contributed by Susobhan Akhuli
// Function to generate an NxN matrixfunction generateMatrix(n) { let matrix = []; let value = 1; for (let i = 0; i < n; ++i) { matrix.push([]); for (let j = 0; j < n; ++j) { matrix[i][j] = value; value++; } } return matrix;}// Main functionfunction main() { // Specify the size of the matrix (N x N) let N = 3; // Generate the matrix using the generateMatrix function let exampleMatrix = generateMatrix(N); // Print the generated matrix for (let i = 0; i < N; ++i) { let row = ""; for (let j = 0; j < N; ++j) { row += exampleMatrix[i][j] + " "; } console.log(row); }}// Call the main functionmain();
# Function to generate an NxN matrixdef generate_matrix(n): matrix = [[0] * n for _ in range(n)] value = 1 for i in range(n): for j in range(n): matrix[i][j] = value value += 1 return matrix# Driver codedef main(): # Specify the size of the matrix (N x N) N = 3 # Generate the matrix using the generate_matrix function example_matrix = generate_matrix(N) # Print the generated matrix for row in example_matrix: print(" ".join(map(str, row)))if __name__ == "__main__": main()
Output
1 2 3 4 5 6 7 8 9
Let’s break down the generateMatrix() function to understand its space complexity:
- The line “vector<vector<int> > matrix(n, vector<int>(n, 0));” in above code creates n*n matrix, Hence the space complexity becomes O(n2)
Relationship Between Input Size and Algorithmic Space Complexity:
Suppose the size of input is N and the space required for algorithm to store this input is X then the space will vary with size of input as given in following table:
Size of Input | Size of Input |
|---|---|
N | X |
2N | 4X |
3N | 9X |
4N | 16X |
It can be represented as Space required = (size of input)2 * X
Although for small inputs it appears like it doesn’t impact on large scale but for bigger input it can heavily impact on performance of algorithm as the time increases as function of square of size of input.
Conclusion:
Big O(N^2) complexity signifies a quadratic growth rate in algorithmic time or space requirements. Algorithms with O(N^2) time complexity, often involving nested loops, may face efficiency challenges for larger inputs. Recognizing and optimizing such algorithms is crucial. Similarly, O(N^2) space complexity indicates quadratic growth in memory usage, guiding decisions on resource allocation and optimization strategies. Understanding O(N^2) complexity is essential for evaluating algorithmic efficiency and scalability.
Related Article:
- Understanding Time Complexity with Simple Examples
- What does Big O – O(N) complexity mean?
- Difference between Big O vs Big Theta Θ vs Big Omega Ω Notations
- What does Constant Time Complexity or Big O(1) mean?
- Practice Questions on Time Complexity Analysis
bhushanc2003
Improve
Next Article
What does Big O - O(N) complexity mean?
