I have an example that I found online, and I wanted to check its frequency and the total Big Oh. However, I'm having trouble calculating the frequency of an if-else statement inside a loop, and I can't seem to find the answer online.
This is what I have so far:
1 int i, j, sum = 0; // Frequency of 1
2 for (i = 0; i < n; i++) { // Frequency of n + 1
3 if (i != 0) // Frequency of n
4 sum += i; // Frequency of n-1
5 else for (j = 0; j < n; j++) // Frequency of n + 1
6 sum += j; // Frequency of n
7 } // O(n)
I know when calculating the Big Oh, I should be looking at the worst case, but isn't at worst the else will run 1 time only? if so is my reasoning and solution correct? or should I assume that for example at line 5 will run (n (n + 1)) times? which will turn this into O(n^2)
This has been bugging me for days, and I've searched everywhere for the correct way to go about this, and I give up trying to figure it out.
Aucun commentaire:
Enregistrer un commentaire