Question

/*
   * Add operation counts
   * f(N) formula (show your work)
   * O(N) reduction -
   */
   public static long sum2(int N)//f(N) = ; O(N) =
   {
       long opCount = 0;
       long sum = 0;
       for(int i = 0; i < N; i++)
       {
           for(int j = 0; j < N; j++)
           {
               sum++;
           }
       }
       System.out.println("f(N) = [your answer]");
       System.out.println("O(N) = [your answer]");
       System.out.println("OpCount : "+opCount);
       return sum;
   }

Answer 1

/*
 * Add operation counts
 * f(N) formula (show your work)
 * O(N) reduction -
 */
public static long sum2(int N)//f(N) = ; O(N) =
{
    long opCount = 0;
    long sum = 0;
    opCount++;  // for long sum = 0
    for (int i = 0; i < N; i++) {
        // so, number of operations in the below for loop = 3N
        for (int j = 0; j < N; j++) {
            sum++;
            opCount += 3;   // one for j++, one for j < N, one for sum++
        }
        // number of operations here = 4
        opCount += 2;   // one for extra j < N, one for int j = 0
        opCount += 2;   // one for i++, one for i < N
    }
    opCount += 2;   // one for extra i < N, one for int i = 0
    // so, total number of operations = (3N+4)*N + 2 = 3N^2 + 4N + 3
    /**
     * Outer for loop iterates N times
     * Inner for loop iterates N times
     * As explained in above comments, number of operations = 3N^2 + 4N + 3
     * so, f(N) = N^2
     * and time complexity is O(N^2)
     */
    System.out.println("f(N) = 3N^2 + 4N + 3");
    System.out.println("O(N) = O(N^2)");
    System.out.println("OpCount : " + opCount);
    return sum;
}