CODEWITHSUNDEEP
algorithmdata-structuresruntimebig-o
hyperspacewoo
hyperspacewoo

Reputation: 9

How to calculate the number of operations in this function?

So my friend gave me the f(n), but I don't understand how he got there. Would like some info on how. We are essentially learning how to write algorithms with big O notation. The problem is just counting work assignments within the code and nested loops are each N intervals. I just don't understand where the division comes from in this case.

public static String[] sum4(int N)
{
    //DO NOT COUNT IN opCount
    long opCount = 0;
    String fn = "f(N) = 5N+5(N(N-1)/2)+4";
    String On = "O(N) = n^2";
    //BEGIN opCounts
    long sum = 0;
    opCount++;// assignment of sum
    opCount++;//assignment of i
    opCount++;//comparison of I < N
    for(int i = 0; i < N; i++)
    {
        
        opCount++;//assignment of j
        opCount++;//comparison of j < i
        for(int j = 0; j < i; j++)//5N
        {
            sum++;
            opCount+=2;// sum addition and assignment
            opCount+=2;// J++ addition and assignment
            opCount++;// Comparison of J < I and the multiplier
        }
        opCount++;// I < N comparison
        opCount+=2;// I++
    }
    opCount++;//return
    return new String[] {fn, On, opCount+""};
}

Upvotes: 0

Views: 1578

Answers (2)

Muhteva
Muhteva

Reputation: 2832

First analyze the total number of operations performed in the innermost loop:

for(int j = 0; j < i; j++)//5N
  {
    sum++;
    opCount+=2;// sum addition and assignment
    opCount+=2;// J++ addition and assignment
    opCount++;// Comparison of J < I and the multiplier
  }

sum addition and assignment --> 2 operations
J++ addition and assignment --> 2 operations
Comparison of J < I and the multiplier --> 1 operation
In total, it takes 5 operations in each loop. So how many loops are there? There are i many loops. To calculate the number of operations dependent on n, now we have to examine outer loop:

   for(int i = 0; i < N; i++)
    {
        
        opCount++;//assignment of j
        opCount++;//comparison of j < i
        for(int j = 0; j < i; j++)//5N
        {
            sum++;
            opCount+=2;// sum addition and assignment
            opCount+=2;// J++ addition and assignment
            opCount++;// Comparison of J < I and the multiplier
        }
        opCount++;// I < N comparison
        opCount+=2;// I++
    }

//assignment of j --> 1 operation
//comparison of j < i --> 1 operation
inner for loop --> 5 * i many operations (we calculated it above)
// I < N comparison --> 1 operation
// I++ --> 2 operation
Therefore in one iteration, it performs 5 + 5*i many operations. To sum up:

Total operations = (5 + 0) + (5 + 5) + (5 + 10) + (5 + 15) + ... + (5 + 5*(N-1))
                     i=0       i=1        i=2        i=3               i=N-1
Total operations = 5*N + 5*(0 + 1 + 2 + .. + (N-1))
Total operations = 5N+5(N(N-1)/2)

Now, add the last assignments:

 // assignment of sum
 //assignment of i
 //comparison of I < N
 //return

In total, there are 4 many operations. Total number of operations: 5N+5(N(N-1)/2)+4

Upvotes: 1

fskj
fskj

Reputation: 964

If you mean the division in the term 5N+5(N(N-1)/2)+4, it comes from the fact that you execute the lines in the innermost loop N(N-1)/2 times. In each iteration of the outermost loop, you will execute the innermost loop i times. So when i is 0, you will execute the inner loop 0 times, when i is 1, you will execute the inner loop 1 time, when i is 2, inner loop 2 times, and so on... In total, the number of times you execute the inner loop is 0 + 1 + 2 + 3 + ... + N-1, and that sum is equal to N*(N-1)/2. Here is some background on how the sum is evaluated to its closed-form: https://brilliant.org/wiki/sum-of-n-n2-or-n3/

Upvotes: 0

Related Questions