Big O menggambarkan bagaimana pekerjaan bertambah seiring bertambahnya input, dengan mengabaikan faktor konstan:
- O(1): pekerjaan yang sama untuk ukuran berapa pun, seperti pencarian di dictionary atau set.
- O(n): satu kali penelusuran atas data.
- O(n log n): pengurutan.
- O(n²): loop di dalam loop atas data yang sama. Sepuluh kali lipat jumlah baris berarti seratus kali lipat pekerjaan.
Beberapa loop tersembunyi di dalam satu baris. x in a_list menelusuri list, jadi melakukannya untuk setiap item dari list lain adalah O(n²). x in a_set rata-rata O(1), jadi membuat set satu kali saja mengubah seluruh pekerjaan menjadi O(n). Hal yang sama berlaku untuk list.index, list.count, dan list.remove di dalam loop.
Trik lain adalah menghitung sekali lalu memakai ulang hasilnya: total kumulatif menjawab setiap pertanyaan "jumlah dari i sampai j" dengan satu pengurangan.
Di pelajaran ini, pemeriksaan tersembunyi memakai input berisi ribuan item. Jawaban kuadratik kehabisan waktu meskipun benar pada data kecil.
Output: ['SO-1']. Setiap in pada set adalah satu langkah, bukan penelusuran seluruh list.