WikiGalaxy
Constant Space Complexity (O(1))
Description:
This class of space complexity involves algorithms that use a constant amount of space, regardless of the input size. This means that the algorithm's space usage does not grow with the input.
public class SumExample {
public static int sum(int a, int b) {
return a + b;
}
public static void main(String[] args) {
System.out.println(sum(5, 10)); // Output: 15
}
}
Console Output:
15
Linear Space Complexity (O(n))
Description:
Linear space complexity indicates that the amount of space used by the algorithm increases linearly with the input size. This is common in algorithms that store data in arrays or lists.
import java.util.ArrayList;
public class LinearSpace {
public static void main(String[] args) {
ArrayList numbers = new ArrayList<>();
for (int i = 0; i < 10; i++) {
numbers.add(i);
}
System.out.println(numbers);
}
}
Console Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Quadratic Space Complexity (O(n^2))
Description:
Quadratic space complexity occurs when the space required is proportional to the square of the input size. This often happens with algorithms that use a two-dimensional array.
public class MatrixExample {
public static void main(String[] args) {
int n = 3;
int[][] matrix = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = i * j;
}
}
for (int[] row : matrix) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
}
}
Console Output:
0 0 0
0 1 2
0 2 4
Logarithmic Space Complexity (O(log n))
Description:
Logarithmic space complexity is typical in algorithms that divide the problem into smaller subproblems, such as binary search. The space grows logarithmically with the input size.
public class BinarySearch {
public static int binarySearch(int[] arr, int left, int right, int x) {
if (right >= left) {
int mid = left + (right - left) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, left, mid - 1, x);
return binarySearch(arr, mid + 1, right, x);
}
return -1;
}
public static void main(String[] args) {
int[] arr = {2, 3, 4, 10, 40};
int result = binarySearch(arr, 0, arr.length - 1, 10);
System.out.println("Element found at index: " + result);
}
}
Console Output:
Element found at index: 3
Exponential Space Complexity (O(2^n))
Description:
Exponential space complexity is usually found in recursive algorithms that solve problems with a large number of subproblems, such as the calculation of Fibonacci numbers using recursion.
public class Fibonacci {
public static int fib(int n) {
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
int n = 5;
System.out.println("Fibonacci number is: " + fib(n));
}
}
Console Output:
Fibonacci number is: 5
