Algorithm notes
Algorithm Time Complexity
Definition of Algorithm Time Complexity
Expressed using Big O notation (O(∙)).
Answers two key questions:
How fast does the algorithm run?
How does its performance compare to other algorithms?
Visual Representation
Axes Description:
X-axis: Represents the input size n of the problem.
Y-axis: Represents the running time function f(n).
The graph highlights six commonly encountered complexity classes.
Key Complexity Classes:
In our studies, we will primarily focus on the following complexities:
O(1)
O(log n)
O(n)
O(n log n)
O(n²)
Understanding Algorithm Complexities
Two Perspectives
How fast an algorithm runs:
Constant Time Complexity (O(1)):
The running time does not change regardless of the input size.
Logarithmic Time Complexity (O(log n)):
The running time increases slowly with the input size.
When n becomes very large, the running time remains nearly constant.
Linear Time Complexity (O(n)):
The running time increases in direct proportion to the input size.
Log-Linear Time Complexity (O(n log n)):
The running time increases moderately compared to linear growth.
Quadratic Time Complexity (O(n²)):
The running time increases proportionally to the square of the input size.
Exponential Time Complexity (O(2ⁿ)):
The running time increases very rapidly as input sizes grow.
How an algorithm compares to others:
As you move down the hierarchy from O(2ⁿ) to O(1), passing through O(n²), O(n log n), O(n), and O(log n), the algorithm increasingly becomes more efficient.
Implications of Complexity Classes:
Comparative Efficiency: Algorithms with lower time complexity (such as O(1)) are preferred over those with higher complexities (such as O(2ⁿ)) when evaluating efficiency.
Application in Real-World Problems: Understanding these complexities allows developers and computer scientists to choose suitable algorithms based on expected input sizes and performance requirements.