- Example Algorithm: Accessing an element in an array by index.
- Time Complexity: O(1) - The operation takes a fixed amount of time regardless of the array size.
- Space Complexity: O(1) - No additional space is used beyond the input array.
public class ConstantTimeExample {
public static void main(String[] args) {
int[] array = {10, 20, 30, 40, 50}; // Sample array
int index = 2; // Index to access
// Accessing the element at the given index
// This operation is O(1) because it directly jumps to the memory location
// without iterating or depending on the array size.
int element = array[index];
System.out.println("Element at index " + index + ": " + element);
}
}
- Example Algorithm: Binary search on a sorted array.
- Time Complexity: O(log n) - The search space is halved with each step.
- Space Complexity: O(1) - Only a few variables are used, no extra space proportional to input.
public class LogarithmicTimeExample {
public static int binarySearch(int[] sortedArray, int target) {
int left = 0; // Start of the search range
int right = sortedArray.length - 1; // End of the search range
// Loop until the search range is exhausted
while (left <= right) {
int mid = left + (right - left) / 2; // Calculate middle index to avoid overflow
// If target is found at mid, return the index
if (sortedArray[mid] == target) {
return mid;
}
// If target is larger, ignore left half
else if (sortedArray[mid] < target) {
left = mid + 1;
}
// If target is smaller, ignore right half
else {
right = mid - 1;
}
}
// Target not found
return -1;
}
public static void main(String[] args) {
int[] sortedArray = {2, 3, 4, 10, 40}; // Sorted array required for binary search
int target = 10;
// Binary search call
// Time complexity is O(log n) because each step halves the search space,
// e.g., for n=1024, it takes at most 10 comparisons.
int result = binarySearch(sortedArray, target);
System.out.println("Index of " + target + ": " + result);
}
}
- Example Algorithm: Linear search in an array.
- Time Complexity: O(n) - In the worst case, it checks every element.
- Space Complexity: O(1) - Only constant extra space for variables.
public class LinearTimeExample {
public static int linearSearch(int[] array, int target) {
// Iterate through each element in the array
for (int i = 0; i < array.length; i++) {
// Check if current element matches the target
if (array[i] == target) {
return i; // Return index if found
}
}
return -1; // Return -1 if not found
}
public static void main(String[] args) {
int[] array = {10, 20, 30, 40, 50}; // Sample array
int target = 30;
// Linear search call
// Time complexity is O(n) because it may need to check all n elements
// in the worst case (target not present or at the end).
int result = linearSearch(array, target);
System.out.println("Index of " + target + ": " + result);
}
}
- Example Algorithm: Merge sort.
- Time Complexity: O(n log n) - Divides the array (log n levels) and merges (n work per level).
- Space Complexity: O(n) - Requires extra space for temporary arrays during merging.
public class LinearithmicTimeExample {
// Merge two sorted subarrays
private static void merge(int[] array, int left, int mid, int right) {
int n1 = mid - left + 1; // Size of left subarray
int n2 = right - mid; // Size of right subarray
int[] leftArray = new int[n1]; // Temporary array for left
int[] rightArray = new int[n2]; // Temporary array for right
// Copy data to temporary arrays
for (int i = 0; i < n1; i++) leftArray[i] = array[left + i];
for (int j = 0; j < n2; j++) rightArray[j] = array[mid + 1 + j];
// Merge the temporary arrays back into the original
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
array[k++] = leftArray[i++];
} else {
array[k++] = rightArray[j++];
}
}
// Copy remaining elements if any
while (i < n1) array[k++] = leftArray[i++];
while (j < n2) array[k++] = rightArray[j++];
}
// Recursive merge sort function
public static void mergeSort(int[] array, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2; // Find midpoint
// Recursively sort left and right halves
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
// Merge the sorted halves
merge(array, left, mid, right);
}
}
public static void main(String[] args) {
int[] array = {12, 11, 13, 5, 6, 7}; // Sample unsorted array
// Merge sort call
// Time complexity is O(n log n): log n recursive levels, each doing O(n) work in merging.
// Space is O(n) due to temporary arrays.
mergeSort(array, 0, array.length - 1);
System.out.print("Sorted array: ");
for (int num : array) System.out.print(num + " ");
}
}
- Example Algorithm: Bubble sort.
- Time Complexity: O(n²) - Two nested loops, each running up to n times.
- Space Complexity: O(1) - Sorts in place, no extra space needed.
public class QuadraticTimeExample {
public static void bubbleSort(int[] array) {
int n = array.length;
// Outer loop for each pass
for (int i = 0; i < n - 1; i++) {
// Inner loop for comparing adjacent elements
for (int j = 0; j < n - i - 1; j++) {
// Swap if current element is greater than next
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] array = {64, 34, 25, 12, 22, 11, 90}; // Sample unsorted array
// Bubble sort call
// Time complexity is O(n²) due to nested loops: outer runs n-1 times,
// inner runs up to n times per pass, leading to quadratic growth.
bubbleSort(array);
System.out.print("Sorted array: ");
for (int num : array) System.out.print(num + " ");
}
}
- Example Algorithm: Naive matrix multiplication.
- Time Complexity: O(n³) - Three nested loops for n x n matrices.
- Space Complexity: O(n²) - Space for input and output matrices.
public class CubicTimeExample {
public static int[][] multiplyMatrices(int[][] A, int[][] B) {
int n = A.length; // Assume square matrices
int[][] result = new int[n][n]; // Output matrix
// Three nested loops: i for rows of A, j for columns of B, k for dot product
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
result[i][j] += A[i][k] * B[k][j]; // Accumulate product
}
}
}
return result;
}
public static void main(String[] args) {
int[][] A = {{1, 2}, {3, 4}}; // Sample matrix A
int[][] B = {{5, 6}, {7, 8}}; // Sample matrix B
// Matrix multiplication call
// Time complexity is O(n³) because of three nested loops, each iterating n times.
// Space is O(n²) for storing the result matrix.
int[][] result = multiplyMatrices(A, B);
System.out.println("Result matrix:");
for (int[] row : result) {
for (int val : row) System.out.print(val + " ");
System.out.println();
}
}
}
- Example Algorithm: Recursive Fibonacci (naive).
- Time Complexity: O(2ⁿ) - Each call branches into two more, leading to exponential calls.
- Space Complexity: O(n) - Due to recursion stack depth.
public class ExponentialTimeExample {
public static int fibonacci(int n) {
// Base cases
if (n <= 1) return n;
// Recursive calls: each branches into two
// This leads to redundant computations and exponential time.
return fibonacci(n - 1) + fibonacci(n - 2);
}
public static void main(String[] args) {
int n = 10; // Small n to avoid long computation
// Fibonacci call
// Time complexity is O(2^n) because the recursion tree has about 2^n nodes.
// Space is O(n) for the maximum recursion depth.
int result = fibonacci(n);
System.out.println("Fibonacci of " + n + ": " + result);
}
}
- Example Algorithm: Generating all permutations of an array (backtracking).
- Time Complexity: O(n!) - There are n! permutations, and each is generated in O(n) time.
- Space Complexity: O(n) - Recursion stack and temporary storage.
import java.util.Arrays;
public class FactorialTimeExample {
// Helper to swap elements
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// Recursive function to generate permutations
public static void generatePermutations(int[] array, int start) {
if (start == array.length - 1) {
// Print permutation when base case is reached
System.out.println(Arrays.toString(array));
return;
}
// For each position, try swapping with all remaining elements
for (int i = start; i < array.length; i++) {
swap(array, start, i); // Swap
generatePermutations(array, start + 1); // Recurse
swap(array, start, i); // Backtrack
}
}
public static void main(String[] args) {
int[] array = {1, 2, 3}; // Small array (n=3 has 6 permutations)
// Permutations generation call
// Time complexity is O(n!) because there are n! possible permutations,
// and each is processed in O(n) time (printing/copying).
// Space is O(n) for recursion depth.
generatePermutations(array, 0);
}
}