Complexity of Algorithm
Algorithm complexity is a measure of the performance of an algorithm in terms of
the time and space it requires as a function of the input size. Understanding the
complexity of algorithms is crucial for selecting the most efficient solution for a
given problem.
Types of Complexity
1. Time Complexity:
● Refers to the amount of time an algorithm takes to complete as a
function of the input size.
2. Space Complexity:
● Refers to the amount of memory an algorithm uses as a function of the
input size.
Time Complexity
Time complexity is usually expressed using Big O notation, which describes the
upper bound of the running time for the worst-case scenario. However, average-case
and best-case complexities can also be analyzed.
Big O Notation
Big O notation provides an upper bound on the growth rate of an algorithm’s running
time, ignoring constant factors and lower-order terms. Here are some common Big O
notations:
1. O(1) – Constant Time:
● The running time is constant and does not change with the input size.
● Example: Accessing an element in an array by index.
2. O(log n) – Logarithmic Time:
● The running time grows logarithmically with the input size.
● Example: Binary search.
3. O(n) – Linear Time:
● The running time grows linearly with the input size.
● Example: Iterating through an array.
4. O(n log n) – Linearithmic Time:
● The running time grows in proportion to n log n.
● Example: Merge sort, quicksort (average case).
5. O(n^2) – Quadratic Time:
● The running time grows quadratically with the input size.
● Example: Bubble sort, insertion sort.
6. O(2^n) – Exponential Time:
● The running time doubles with each additional element in the input
size.
● Example: Solving the traveling salesman problem with a brute-force
approach.
7. O(n!) – Factorial Time:
● The running time grows factorially with the input size.
● Example: Generating all permutations of a set.
Examples
1. Linear Search:
● Time Complexity:
● Best Case: O(1)
● Average Case: O(n)
● Worst Case: O(n)
2. Binary Search:
● Time Complexity:
● Best Case: O(1)
● Average Case: O(log n)
● Worst Case: O(log n)
3. Bubble Sort:
● Time Complexity:
● Best Case: O(n)
● Average Case: O(n^2)
● Worst Case: O(n^2)
4. Merge Sort:
● Time Complexity:
● Best Case: O(n log n)
● Average Case: O(n log n)
● Worst Case: O(n log n)
Space Complexity
Space complexity measures the amount of memory an algorithm uses relative to the
input size. It includes both the memory needed for the input data and any auxiliary
space required for processing.
Examples
1. Linear Search:
● Space Complexity: O(1) (no additional space required other than input)
2. Binary Search (Iterative Version):
● Space Complexity: O(1) (no additional space required other than input)
3. Binary Search (Recursive Version):
● Space Complexity: O(log n) (due to the call stack)
4. Merge Sort:
● Space Complexity: O(n) (additional space for merging)
5. Quick Sort:
● Space Complexity:
● O(log n) (best case for recursive call stack)
● O(n) (worst case for recursive call stack if the pivot is the
smallest or largest element each time)
Amortized Analysis
Amortized analysis provides the average time per operation over a worst-case
sequence of operations, ensuring that the total time for a sequence of operations is
averaged out. This is particularly useful for analyzing data structures like dynamic
arrays and certain algorithms where occasional expensive operations are offset by
many cheap operations.
Example
1. Dynamic Array (ArrayList in Java, Vector in C++):
● Insertion at the end has an average-case time complexity of O(1) due
to occasional resizing operations, which take O(n) but happen
infrequently.
Practical Considerations
1. Constants and Lower Order Terms:
● Big O notation focuses on the asymptotic behavior for large inputs,
ignoring constants and lower-order terms. For smaller inputs, these
factors can significantly affect performance.
2. Best, Worst, and Average Cases:
● It is important to consider the different scenarios in which an algorithm
might operate to get a comprehensive understanding of its
performance.
3. Trade-offs:
● There are often trade-offs between time and space complexity. An
algorithm that is faster may use more memory, and vice versa.
Understanding these trade-offs is crucial for optimizing performance
based on the specific constraints of a problem.
