The performance of an algorithm can be measured by its computing time and storage requirements , which is termed as the complexity of an algorithm.
Complexity of an algorithm is the measure of the amount of time and space needed by an algorithm for an input of size ‘n’.
- Space Complexity – Space complexity is the amount of memory needed by an algorithm to run to completion for a given input size ‘n’.
- Time Complexity – Time complexity of an algorithm is the amount of time it needs to execute for a given input size ‘n’.
- Worst Case Time Complexity
- Average Case Time Complexity
- Best Case Time Complexity
Worst Case Time Complexity
Worst Case time complexity represents the maximum amount of time an algorithm requires to process any input of a given size ‘n’. It is the upper bound on the running time for any input, ensuring the algorithm will not exceed this limit.
Average Case Time Complexity
Average Case time complexity describes the expected time an algorithm takes over randomly distributed inputs. It is the tight bound on running time of an algorithm.
Best Case Time Complexity
Best Case time complexity describes the minimum amount of time taken by an algorithm for any input of a given size n. It is the lower bound on the running time.
To represent the running time of an algorithm, we use a function f(n), where n is the input size, to represent the number of units of time taken by a program or an algorithm on any input of size n.
For example, an algorithm may have a running time of f(n)= cn³, where c is some constant. This, n³ represents the main growth rate of time complexity as ‘n’ increases. This n³ is the g(n) which represents the most significant term. g(n) is the bound function and f(n) is the target function.
Complexity Analysis of an algorithm is required when :-
- we want to predict the rate of growth of complexity as the input size increases
- there are multiple algorithms for a specific problem and we need to find the most efficient algorithm
Time Complexity can be of different categories which occur in different scenarios :-
1. Constant Time : O(1)
The execution time remains exactly the same regardless of how large the input dataset grows.
Example: Accessing an array element by its index or pushing an item onto a stack.
2. Linear Time : O(n)
The runtime scales directly and proportionally with the size of the input data, i.e if the size of the input is doubled then running time will also be doubled.
Example: Traversing an unsorted list via a standard loop to find a value (Linear Search).
3. Logarithmic Time : O(log n)
This is the case in algorithms where a set of data is repeatedly divided into half and the middle element is processed. The algorithm reduces the size of the problem by half at each step.
Example: Finding an item in a sorted array using Binary Search.
4. Linear Logarithmic Time : O(n log n)
This complexity combines linear and logarithmic growth behaviours. It frequently occurs when an algorithm divides a problem into subproblems (log n steps) and processes each element linearly (n).
Example: Highly efficient sorting frameworks like Merge Sort or Heap Sort.
5. Quadratic : O(n²)
This is the case when full set of data has to be traversed for each element of the set or we can say that all pairs of data items are processed. The execution time is proportional to the square of the input size.
Example: Bubble Sort and Selection Sort.
6. Cubic : O(n³)
The execution time scales according to the cube of the input size. It generally occurs when an algorithm uses three nested execution loops.
Example: Naive matrix multiplication algorithms or basic three-variable equation solvers.
7. Exponential : O(2^n)
The runtime doubles with every single additional item added to the input dataset. Growth is extremely rapid, making these algorithms highly inefficient for larger values of n.
Solving the Traveling Salesman problem via a naive brute-force method, or computing Fibonacci numbers using recursive functions without optimization.