Time Complexity

Time complexity is a metric used to describe the efficiency of an algorithm by examining how the run time increases with the size of the input. It primarily focuses on the growth trend of the runtime rather than precise execution times, which can vary across different hardware and software environments.

Basics of Time Complexity

Platform Considerations

• Hardware and software environments significantly influence execution efficiency.
• Different operations take varying amounts of time; for instance, + operations may be faster than * operations.

Practical Limitations

• It's impractical to tie the execution time to specific platforms as algorithms should run efficiently across various environments.
• Precise execution times for operations are often unknown, making detailed time estimations challenging.

Example Code

def algorithm(n: int):
    a = 2      # 1 ns
    a += 1     # 1 ns
    a *= 2     # 10 ns
    for _ in range(n):  # Total time = 6n + 12 ns
        print(0)        # 5 ns per loop

Analyzing Time Growth Trend

Time complexity doesn't measure the actual runtime but looks at how the runtime increases with input size. Consider three algorithms:

• Constant order ($O(1)$): Runtime doesn’t depend on input size.
• Linear order ($O(n)$): Runtime grows linearly with input size.
• Constant order for high iteration counts ($O(1)$): Despite high iteration counts, the runtime doesn't depend on input size.

For instance:

def constant_order_algorithm():
    print(0)  # Time complexity: O(1)

def linear_order_algorithm(n):
    for _ in range(n):
        print(0)  # Time complexity: O(n)

Asymptotic Upper Bound

Time complexity can be described using Big-O notation, which provides an upper bound on the time. It doesn't account for exact execution times but rather focuses on the growth rate of the runtime as the input size increases.

Big-O Notation

• Definition: For a function $T (n)$ representing the runtime of an algorithm, if there exist constants $c$ and $n_0$ such that $T (n) \leq c \cdot f (n)$ for all $n > n_0$, then $f (n)$ is considered an asymptotic upper bound of $T (n)$. This relationship is denoted as $T (n) = O (f (n))$.
• Example: Consider the runtime function $T (n) = 3 + 2n$. As $n$ increases, the term $2n$ becomes the dominant factor in the function, making the linear component dictate the growth rate. Therefore, the time complexity of the algorithm is $O (n)$, indicating that the runtime grows linearly with the size of the input $n$.

Calculation Method

1. Count operations: Simplify the operation counts by ignoring constants and coefficients.
2. Determine the highest order term: The highest degree term in the polynomial expression of T (n) dictates the time complexity.

Common Time Complexities

• Constant ($O (1)$): The runtime is independent of the input size. This is typical for algorithms that perform a fixed number of operations, regardless of the input.
• Logarithmic ($O (\log n)$): The runtime increases logarithmically as the input size increases. Algorithms that divide the problem space in half with each step, such as binary search, exhibit logarithmic complexity.
• Linear ($O (n)$): The runtime grows linearly with the input size. This complexity is common in algorithms that process each input element once, such as single-loop traversals of arrays.
• Linear-Logarithmic ($O (n \log n)$): This complexity arises in algorithms that combine linear and logarithmic behaviors, typical of efficient sorting algorithms like mergesort and heapsort.
• Quadratic ($O (n^2)$): The runtime grows as the square of the input size, common in algorithms with nested loops where each loop runs up to $n$ times, such as bubble sort or checking all pairs in a list.
• Exponential ($O (2^n)$): The runtime doubles with each additional element of input, which is characteristic of recursive algorithms that solve a problem by dividing it into two or more smaller sub-problems of the same type, such as the recursive calculation of Fibonacci numbers.
• Factorial ($O (n!)$): The runtime grows factorially with the input size, typical of algorithms that generate all permutations of the input data, such as solving the traveling salesman problem via brute-force search.

Conclusion

Understanding time complexity is crucial for developing efficient algorithms, particularly when dealing with large inputs or performance-critical applications. It helps in selecting the appropriate algorithm based on the expected input size and performance requirements.

Reference and Useful Links

• 2.3 Time complexity - Hello Algo