| n | Pior algoritmo que passa | Notas |
|---|---|---|
| ≤ [10..11] | O(n!), O(n6) | ex. Enumerar permutações |
| ≤ [15..18] | O(2nn2) | ex. PD do Caixeiro-Viajante |
| ≤ [18..22] | O(2nn) | ex. PD com técnica de máscara de bits |
| ≤ 100 | O(n4) | ex. PD com 3 dimensões + laço O(n), nCk=4 |
| ≤ 400 | O(n3) | ex. Floyd-Warshall |
| ≤ 2⋅103 | O(n2lg n) | ex. 2 laços aninhados + consulta em árvore |
| ≤ 5⋅104 | O(n2) | ex. Bubble/Selection/Insertion Sort |
| ≤ 105 |
O(n lg2 n) = O((lg n)(n lg n)) |
ex. Construção de vetor de sufixos padrão |
| ≤ 106 | O(n lg n) | ex. Merge Sort, construir árvore de segmento |
| ≤ 107 | O(n lg lg n) | ex. Crivo de Eratóstenes, função totiente |
| ≤ 108 | O(n), O(lg n), O(1) | ex. Solução matemática. A maioria porém é n ≤ 109 devido ao gargalo de E/S |
Adaptado de 2013, Competitive Programming 3. Steven Halim, Felix Halim. Leva em conta 108 operações por segundo (original é 3 segundos com tempo limite de 3 segundos).
| n | Complexidade de tempo necessária |
|---|---|
| ≤ 10 | O(n!) |
| ≤ 20 | O(2n) |
| ≤ 500 | O(n3) |
| ≤ 5000 | O(n2) |
| ≤ 106 | O(n lg n) ou O(n) |
| é grande | O(1) ou O(lg n) |
Adaptado de 2018, Competitive Programmer's Handbook. Antti Laaksonen.
Estimativas de instruções por segundo: