Time Complexity

Competitive Programming/Time Complexity.md

The time complexity of an algorithm estimates how much time the algorithm will use for a given input. It is usually denoted as $O(\cdot)$ where the dot represent some function.

Calculation Rules

If a code consists of a single command, its time complexity is $O(1)$ .
The time complexity of a loop estimates the number of times the code inside the loop is executed.
If there are $k$ nested loops and each loop goes through $n$ values, then the time complexity ios $O(n^k)$ .

A time complexity does not tell us the exact number of times the code inside a loop is executed, because it only shows the order of growth and ignores the constant factors.
If an algorithm consists of consecutive phases, the total time complexity is the largest time complexity of a single phase.
The time complexity of a recursive function depends on the number of times the function is called and the time complexity of a single call. The total time complexity is the product of these values.

Time Complexity	Description
O(1)	A constant-time algorithm does not depend on the input size. A typical constant-time algorithm is a direct formula that calculates the answer.
O(log n)	A logarithmic algorithm often halves the input size at each step. The running time is logarithmic because `log₂ n` equals the number of times n must be divided by 2 to get 1. The base of the logarithm is not shown.
O(√n)	A square root algorithm is slower than O(log n) but faster than O(n). A special property is that `√n = n / √n`, so n elements can be divided into `O(√n)` blocks of `O(√n)` elements.
O(n)	A linear algorithm goes through the input a constant number of times. It is often the best possible time complexity, as it's usually necessary to access each element at least once.
O(n log n)	This time complexity often indicates that the algorithm sorts the input (e.g., mergesort, heapsort). Another possibility is using a data structure with `O(log n)` operations.
O(n²)	A quadratic algorithm often contains two nested loops. It iterates through all pairs of input elements.
O(n³)	A cubic algorithm often contains three nested loops. It iterates through all triplets of input elements.
O(2ⁿ)	This complexity often means the algorithm iterates through all subsets of the input elements. For example, subsets of {1,2,3} are ∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, and {1,2,3}.
O(n!)	This complexity often means the algorithm iterates through all permutations of the input elements. For example, permutations of {1,2,3} are (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1).

Hint: If the input size is $n = 10^5$ , it is probably expected that the time complexity of the algorithm is $O(n)$ or $O(n\log n)$ .