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