Stavo rivedendo il grande cheatsheet di O al link e ho trovato alcune voci sotto ordinamento che non capisco.
I runtime sono codificati a colori, il verde è migliore del giallo. Ci sono casi in cui Ω (N) è codificato a colori meglio di Ω (N + K) e persino Ω (NK). Un esempio è bubble sort best case vs counting best case.
Supponendo che questi non siano falsi, qualcuno può spiegare perché Ω (N + K) è migliore di Ω (N)?
Penso che tu abbia semplicemente trovato un errore nel sito web.
Le voci N + K e NK dovrebbero essere codificate in giallo, non in verde. Per quanto posso dire, ogni altra voce segue rigorosamente il grafico in alto.
Oggi l'hai imparato solo perché è scritto su un sito web (o un libro o un giornale), non è necessariamente corretto o vero. Questa è una lezione importante da tenere a mente in ogni momento.
Leggi altre domande sui tag big-o