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 matrix
vector<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 code
int 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 approach
import 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 approach
using 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 matrix
function 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 function
function 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 function
main();
# Function to generate an NxN matrix
def 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 code
def 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)
What Does Big O(N^2) Complexity Mean?
Prerequisite:
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