Ada varian alami dari analisis kasus terburuk yang juga berguna. Mungkin yang paling terkenal adalah kompleksitas parametrized. Di sini, kami mempertimbangkan ukuran "dua dimensi": panjang input biasa dan beberapa bilangan bulat non-negatif k , parameter. Meskipun suatu algoritma dapat berjalan sangat buruk dalam kasus terburuk (untuk semua nilai n dan k ), bisa jadi semua kasus dalam aplikasi seseorang yang perlu dipecahkan, parameter k ini kebetulan rendah, sehingga algoritme berjalan dengan baik pada contoh-contoh itu.nknkk
Misalnya, Anda ingin menyelesaikan Set Independen Maksimum pada beberapa kelas grafik, dan kembangkan algoritma yang menarik yang ternyata sangat cepat. Menyelidiki lebih jauh ke dalam kelas grafik sendiri, Anda menemukan bahwa semua grafik yang Anda periksa kebetulan memiliki paling banyak grafik . Nah, Bodlaender (lih. Neidermeier [1]) menunjukkan bahwa ketika treewidth adalah k, Max Independent Set adalah parameter tetap yang dapat ditelusur : dapat diselesaikan dalam waktu O ( 2 k ( | E | + | V | ) ) waktu. Ini memberikan beberapa penjelasan mengapa algoritma Anda bekerja dengan baik.10O ( 2k( | E| + | V| ))
[1] R. Niedermeier, Undangan untuk algoritma parameter-tetap. Seri Kuliah Oxford dalam Matematika dan Penerapannya, Oxford University Press, Oxford, 2006.