WikiGalaxy
Introduction to Time and Space Complexity
Understanding Complexity:
Time and space complexity are crucial concepts in computer science that help us analyze the efficiency of an algorithm. Time complexity refers to the computational time taken by an algorithm as a function of the length of the input, while space complexity refers to the amount of memory space required.
Big O Notation:
Big O notation is used to classify algorithms according to their running time or space requirements in the worst-case scenario. It provides an upper bound on the time or space an algorithm might need.
public class Example {
public static void main(String[] args) {
int n = 100;
for (int i = 0; i < n; i++) {
System.out.println("Iteration: " + i);
}
}
}
Linear Time Complexity - O(n):
The above code demonstrates a linear time complexity O(n) as the number of iterations is directly proportional to the input size n.
Constant Space Complexity - O(1):
The space complexity is O(1) since the space required does not scale with the input size.
Console Output:
Iteration: 0 Iteration: 1 ... Iteration: 99
Quadratic Time Complexity
Nested Loops:
When analyzing algorithms with nested loops, the time complexity often becomes quadratic O(n²). This is because each element in the outer loop triggers a full iteration of the inner loop.
public class QuadraticExample {
public static void main(String[] args) {
int n = 10;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print("(" + i + "," + j + ") ");
}
System.out.println();
}
}
}
Quadratic Time Complexity - O(n²):
The time complexity is O(n²) due to the nested loops iterating over the input size n.
Constant Space Complexity - O(1):
The space complexity remains constant at O(1) as no additional space is used that scales with input size.
Console Output:
(0,0) (0,1) ... (9,9)
Logarithmic Time Complexity
Binary Search:
Binary search is a classic example of logarithmic time complexity O(log n), which significantly reduces the time taken to search for an element in a sorted array.
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int result = binarySearch(arr, 7);
System.out.println("Element found at index: " + result);
}
}
Logarithmic Time Complexity - O(log n):
The time complexity is O(log n) as the search space is halved with each step.
Constant Space Complexity - O(1):
The space complexity is O(1) since the algorithm uses a fixed amount of space.
Console Output:
Element found at index: 6
Exponential Time Complexity
Recursive Fibonacci:
Exponential time complexity O(2^n) is commonly observed in recursive algorithms like the naive computation of Fibonacci numbers.
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 of " + n + " is: " + fib(n));
}
}
Exponential Time Complexity - O(2^n):
The time complexity is O(2^n) due to the repeated calculations in the recursive calls.
Logarithmic Space Complexity - O(n):
The space complexity is O(n) due to the recursion stack.
Console Output:
Fibonacci of 5 is: 5
Factorial Time Complexity
Permutations:
Factorial time complexity O(n!) is often seen in problems involving permutations, where every possible arrangement of elements is considered.
import java.util.*;
public class Permutations {
private static void permute(String str, String result) {
if (str.length() == 0) {
System.out.println(result);
return;
}
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
String ros = str.substring(0, i) + str.substring(i + 1);
permute(ros, result + ch);
}
}
public static void main(String[] args) {
String s = "ABC";
permute(s, "");
}
}
Factorial Time Complexity - O(n!):
The time complexity is O(n!) due to the generation of all possible permutations.
Factorial Space Complexity - O(n):
The space complexity is O(n) for the recursion stack.
Console Output:
ABC ACB BAC BCA CAB CBA
