dimanche 8 mars 2015

How would I go about analyzing the formal complexity of this algorithm under Big Theta Θ notation?



I’m needing some help understanding algorithm analysis using Big Theta Θ notation:



Big O is the most commonly used asymptotic notation for comparing functions, although in many cases Big O may be replaced with Big Theta Θ for asymptotically tighter bounds.



How would I analyze this algorithm step by step? I know the final answer is ϴ(n²), but I’m having trouble seeing it. Any help would be appreciated.


You may assume for simplicity that n = 2k, for some positive integer k.



int a = 0;
int i = n * n;
while (i > 0) {
for (int j = 0; j < i; j++) {
a++;
}
i = i/2;
}



Aucun commentaire:

Enregistrer un commentaire