Time Complexity

The efficiency of algorithms is important in Competitive Programming. The large challenge of competitive programming / interviewing isn’t necessarily coming up with a solution, but rather coming up with an efficient solution. The time complexity of an algorithm estimates how much time the algorithm uses for some input. Typically we are concerned with the worst case computation time with respect to the input as it tends towards infinity so that it becomes the dominating term. We use “Big O Notation” to do so ( $O (n)$ ).

Recursion

The time complexity of a recursive function depends on the number of times the function is called and the time complexity of that call, the total time complexity a product of these values.

Complexity Classes

$O (1)$ : Constant time
$O (lo g n)$ : Halves the input size on each step
$O (n)$ : ???
$O (n)$ : Linear time
$O (n lo g n)$ : This type of algorithm usually sorts the input and then implements a solution
$O (n^{2})$ : Usually indicates two nested loops
$O (n^{3})$ : Usually indicates three nested loop
$O (2^{n})$ : Usually indicates the algorithm iterating through all subsets of the input elements
$O (n!)$ : Usually indicates the algorithm iterating through all permutations of the input elements

Notes

Loops make things slow

Polynomial

An algorithm is polynomial if its time complexity is at most $O (n^{k})$ where k is a constant. In practice, k is usually small so a polynomial time complexity roughly means an efficient algorithm. There are many problems that do not have polynomial solutions (NP Hard problems)

You can try to estimate efficiency based on input size…

Input Size	Required Time Complexity
$n \leq 10$	$O (n!)$
$n \leq 20$	$O (2^{n})$
$n \leq 500$	$O (n^{3})$
$n \leq 5000$	$O (n^{2})$
$n \leq 1 0^{6}$	$O (n lo g n)$ or $O (n)$
$n$ is large	$O (lo g n)$ or $O (1)$

🤖 Dan Huynh

Explorer

Time Complexity

Recursion

Graph View

Backlinks