Quale sarà il risultato della complessità temporale di questo pezzo di codice, cioè
int sum(int A[], int n)
{
int sum = 0, i;
for(i = 0; i < n; i++) {
sum = sum + A[i];
}
return sum;
}
Un modo per iniziare a capire se la complessità è O (1) o O (N) o un ordine superiore è capire cosa succede se il valore di n passa da n a n + 1. Se è O (1) allora il tempo di esecuzione per il passaggio da n a n + 1 sarà lo stesso, se è O (N) allora il tempo di esecuzione cambierà da n * k secondi a (n + 1) * k secondi (per qualche costante k). se la modifica è qualcos'altro, non è O (1) o O (N) e sono necessarie ulteriori analisi.
Questo dovrebbe darti abbastanza informazioni per capirlo, se no, poi chiedere via.
Leggi altre domande sui tag complexity big-o time