Sto cercando di capire perché è impossibile creare uno strumento che calcoli automaticamente la notazione Big-O.
Ho letto dei problemi di Halting, ma non sono relativo alla notazione Big-O e mi stavo chiedendo, o almeno ho un esempio in cui non siamo in grado di determinare una notazione Big-O per una data funzione.
Qualcuno può darmi un esempio?
Se avessi uno strumento del genere, potresti eseguirlo su qualsiasi algoritmo per capire che cos'è Big-O. Se restituisce un valore inferiore all'infinito, apparentemente l'algoritmo si arresta nel tempo proporzionale a quello. Quindi avresti risolto il problema dell'arresto, ma sappiamo che è impossibile. Quindi non puoi avere uno strumento del genere.
Leggi altre domande sui tag complexity big-o