WikiGalaxy
Time Complexity Classes
Constant Time Complexity - O(1)
Constant time complexity signifies that the algorithm's performance is constant and does not change with the size of the input data. It is considered the most efficient time complexity.
int getFirstElement(int[] array) {
return array[0];
}
Console Output:
First element of the array is returned.
Linear Time Complexity - O(n)
Linear Time Complexity
In linear time complexity, the time taken by the algorithm increases linearly with the size of the input data. It is common in algorithms that need to process each element of the input.
int sumArray(int[] array) {
int sum = 0;
for(int i = 0; i < array.length; i++) {
sum += array[i];
}
return sum;
}
Console Output:
Sum of all elements in the array is calculated.
Quadratic Time Complexity - O(n²)
Quadratic Time Complexity
Quadratic time complexity occurs when the time taken by an algorithm is proportional to the square of the size of the input data. This is typical in algorithms with nested loops.
void printPairs(int[] array) {
for(int i = 0; i < array.length; i++) {
for(int j = 0; j < array.length; j++) {
System.out.println(array[i] + ", " + array[j]);
}
}
}
Console Output:
All pairs of elements in the array are printed.
Logarithmic Time Complexity - O(log n)
Logarithmic Time Complexity
Logarithmic time complexity is achieved when the algorithm's time grows logarithmically with the input size. This is common in algorithms that divide the problem into smaller chunks, such as binary search.
int binarySearch(int[] array, int target) {
int left = 0, right = array.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(array[mid] == target) return mid;
if(array[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
Console Output:
Index of the target element in the array is returned, or -1 if not found.
Exponential Time Complexity - O(2^n)
Exponential Time Complexity
Exponential time complexity signifies that the algorithm's time grows exponentially with the input size. This is often seen in recursive algorithms that solve problems by breaking them down into smaller subproblems.
int fibonacci(int n) {
if(n <= 1) return n;
return fibonacci(n-1) + fibonacci(n-2);
}
Console Output:
The nth Fibonacci number is calculated.
