Quindi ho appena preso una struttura di dati midterm oggi e mi è stato chiesto di determinare il tempo di esecuzione, in notazione Big O, del seguente ciclo annidato:
for (int i = 0; i < n-1; i++) {
for(int j = 0; j < i; j++2) {
//1 Statement
}
}
Ho difficoltà a capire la formula che sta alla base della determinazione del tempo di esecuzione. Ho pensato che dal momento che il ciclo interno ha 1 istruzione, e usando l'equazione di serie di: (n * (n - 1)) / 2, ho pensato che fosse: 1n * (n-1) / 2. Così equalizzazione (n ^ 2 - 1) / 2. E così ho generalizzato il runtime come O (n ^ 2/2). Non sono sicuro che sia corretto, haha, dovrei dividere nuovamente la mia risposta per 2 poiché j viene aumentato ad intervalli di 2? O la mia risposta è completamente fuori?