Prendi il seguente algoritmo con due sezioni separate e le sezioni non si influenzano a vicenda (la funzione non è ricorsiva).
void algorithm(int x)
{
// This section of the algorithm has linear growth... O(x)
// This section of the algorithm has x * logarithmic growth... O(xlogx)
}
Per determinare la notazione Big O dell'algoritmo, ho fatto quanto segue:
Tempo di esecuzione dell'algoritmo approssimativamente = xlogx + x
Il termine più grande è xlogx, quindi l'algoritmo è Big O = O (xlogx).
È corretto? O devo inserire più informazioni dalle due sezioni dell'algoritmo. Ad esempio, la prima sezione esegue effettivamente operazioni 10x, ma nei miei calcoli uso solo la notazione O (x).