Question

* Add operation counts -
   * f(N) formula (show your work) -
   * O(N) reduction -
   */
   public static long sum4(int N)//f(N) = ; O(N) =
   {
       long opCount = 0;
       long sum = 0; // 1
       for(int i = 0; i < N; i++)
       {
           for(int j = 0; j < i; j++)
           {
               sum++;
           }
       }
       System.out.println("f(N) = [your answer]");
       System.out.println("O(N) = [your answer]");
       System.out.println("OpCount : "+opCount);
       return sum;
   }
   /*
  
   * Add operation counts
   * f(N) formula (show your work)
   * O(N) reduction
   */
   public static long sum5(int N)//f(N) = ; O(N) =
   {
       long opCount = 0;
       long sum = 0; //1
       for(int i = 0; i < N; i++) //2N + 2
       {
           for(int j = 0; j < i*i; j++) //N^2 + N + 1
           {
               for(int k = 0; k < j; k++) //
               {
                   sum++;
               }
           }
       }
       System.out.println("f(N) = [your answer]");
       System.out.println("O(N) = [your answer]");
       System.out.println("OpCount : "+opCount);
       return sum;
   }
   /*
  
   * Add operation counts
   * f(N) formula (show your work)
   * O(N) reduction
   */
   public static long sum6(int N)//f(N) = ; O(N) =
   {
       long opCount = 0;
       long sum = 0;
       for(int i = 1; i < N; i++)//i starts at 1 to prevent division error in if statement
       {
           for(int j = 0; j < i*i; j++)
           {
               if(j%i == 0)
               {
                   for(int k = 0; k < j; k++)
                   {
                       sum++;
                   }
               }
           }
       }
       System.out.println("f(N) = [your answer]");
       System.out.println("O(N) = [your answer]");
       System.out.println("OpCount : "+opCount);
       return sum;
   }

Answer 1

public static long sum4(int N)//f(N) = ; O(N) =
{
long opCount = 0;
long sum = 0; //
for(int i = 0; i < N; i++) //runs N times
{
for(int j = 0; j < i; j++) //runs i times, possible i values are 0,1,2,3,,,,,N-1
{
sum++;
}
}
System.out.println("f(N) = [your answer]");
System.out.println("O(N) = [your answer]");
System.out.println("OpCount : "+opCount);
return sum;//
}
total run time f(n): 0+1+2+3+4+...+N-1 = N*(N-1)/2
f(n)=N*(N-1)/2
O(N)=O(N^2)

public static long sum5(int N)//f(N) = ; O(N) =
{
long opCount = 0;
long sum = 0; //1
for(int i = 0; i < N; i++) //runs N times
{
for(int j = 0; j < i*i; j++) //runs i*i times, possible value for i:0,1,2,3,,,,N-1
{
for(int k = 0; k < j; k++) //runs j times, possible values for j:0,1,4,8,,,, (N-1)*(N-1)
{
sum++;
}
}
}
System.out.println("f(N) = [your answer]");
System.out.println("O(N) = [your answer]");
System.out.println("OpCount : "+opCount);
return sum;
}
inner most loop runs j times for every iteration of outer loop
middle loop runs runs i*i times for every iteration of outer loop
outer loop runs N times
now
i=0:
-j=0:
--k=0;//denotes number of times it runs
i=1:
-j=0:
--k=0;
i=2:
-j=0,1,2,3:
--k=0+1+2+3 ;
i=3:
-j=0,1,2,3,4,5:
--k=0+1+2+3+4+5;
this means
for each i value below two loop run time will be : i*i*(i*i-1)/2
so total complexity f(n): 0*0*(0*0-1)/2 + 1*1(1*1-1)/2 +2*2*(2*2 -1)/2 +....+(N-1)*(N-1)((N-1)*(N-1)-1)/2
F(N) = 0+0+4(4-1)/2 +9*(9-1)/2 +....+ (N-1)^2 * ((N-1)^2 -1)/2
O(N) = O(N^5)

public static long sum6(int N)//f(N) = ; O(N) =
{
long opCount = 0;
long sum = 0;
for(int i = 1; i < N; i++)//i starts at 1 to prevent division error in if statement
{
for(int j = 0; j < i*i; j++)
{
if(j%i == 0)//the number of times below loop executed is : i times only
{//condition satified for i times
for(int k = 0; k < j; k++)
{
sum++;
}
}
}
}
System.out.println("f(N) = [your answer]");
System.out.println("O(N) = [your answer]");
System.out.println("OpCount : "+opCount);
return sum;
}

f(N) = 1*(1+1)/2 + 2*(2+1)/2 +....+ (N-1)*(N-1)/2
O(N) = O(N^4)