mercredi 14 février 2018

Calculating the frequency if statements in a loop and the total Big Oh

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