Understanding time complexities is crucial for analyzing the efficiency of algorithms and data structures. Below is an explanation of common time complexities with Java examples, outputs, and detailed explanations. Each complexity is also rated for its efficiency, where O(1) is considered 100% efficient.
Common Time Complexities
| Time Complexity | Description | Example Operations | Efficiency (%) |
|---|---|---|---|
| O(1) | Constant time, independent of input size | Accessing an element in an array | 100% |
| O(log n) | Logarithmic time, reduces problem size by half | Binary search | 90% |
| O(n) | Linear time, scales directly with input size | Iterating through a list | 75% |
| O(n log n) | Linearithmic time, common in efficient sorting | Merge sort, Quick sort | 50% |
| O(n^2) | Quadratic time, nested loops | Bubble sort, Selection sort | 25% |
| O(2^n) | Exponential time, grows exponentially | Recursive algorithms (e.g., Fibonacci) | 10% |
| O(n!) | Factorial time, extremely slow | Permutations, Traveling Salesman | 5% |
Examples
1. O(1) – Constant Time
Example:
public class ConstantTimeExample {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
System.out.println(arr[2]); // Accessing an element
}
}
Output:
3
Explanation: Accessing an element by index in an array takes constant time because it directly calculates the memory location.
2. O(log n) – Logarithmic Time
Example:
import java.util.Arrays;
public class LogarithmicTimeExample {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
System.out.println(Arrays.binarySearch(arr, 4)); // Binary search
}
}
Output:
3
Explanation: Binary search divides the search space in half with each step, leading to logarithmic time complexity.
3. O(n) – Linear Time
Example:
public class LinearTimeExample {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
for (int num : arr) {
System.out.println(num);
}
}
}
Output:
1 2 3 4 5
Explanation: The loop iterates through the array, visiting each element once. Time complexity is proportional to the size of the array.
4. O(n log n) – Linearithmic Time
Example:
import java.util.Arrays;
public class LinearithmicTimeExample {
public static void main(String[] args) {
int[] arr = {5, 3, 1, 4, 2};
Arrays.sort(arr); // Merge sort or TimSort internally
System.out.println(Arrays.toString(arr));
}
}
Output:
[1, 2, 3, 4, 5]
Explanation: Efficient sorting algorithms like MergeSort or TimSort split the array into smaller parts and sort them recursively, resulting in O(n log n) complexity.
5. O(n^2) – Quadratic Time
Example:
public class QuadraticTimeExample {
public static void main(String[] args) {
int[] arr = {5, 3, 1, 4, 2};
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
for (int num : arr) {
System.out.println(num);
}
}
}
Output:
1 2 3 4 5
Explanation: The nested loops result in quadratic time complexity, as every element is compared with every other element.
6. O(2^n) – Exponential Time
Example:
public class ExponentialTimeExample {
public static void main(String[] args) {
System.out.println(fibonacci(5));
}
public static int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
Output:
5
Explanation: The recursive function calls itself twice for each input, leading to exponential growth in the number of calls.
7. O(n!) – Factorial Time
Example:
import java.util.ArrayList;
import java.util.List;
public class FactorialTimeExample {
public static void main(String[] args) {
permute(new ArrayList<>(), "ABC");
}
public static void permute(List<Character> prefix, String str) {
if (str.isEmpty()) {
System.out.println(prefix);
} else {
for (int i = 0; i < str.length(); i++) {
List<Character> newPrefix = new ArrayList<>(prefix);
newPrefix.add(str.charAt(i));
permute(newPrefix, str.substring(0, i) + str.substring(i + 1));
}
}
}
}
Output:
[A, B, C] [A, C, B] [B, A, C] [B, C, A] [C, A, B] [C, B, A]
Explanation: Generating all permutations of a string involves factorial time complexity, as the number of permutations for a string of length n is n!.
Summary
Understanding time complexity helps in writing efficient code and choosing the right algorithms for a given problem. Always strive for the least complex solution that satisfies the requirements.