In Problem3.java, implement the three code fragments from written problem 3. Hav

Question

In Problem3.java, implement the three code fragments from written problem 3. Have your code repeatedly run each fragment on various values of n. Time each run and see if the progression of timings as n increases matches the predicted run times from your written assignment. Place the results of your timing and your explanation in a file called Problem3.txt. For the third fragment, set k equal to 2 for all of your testing. The easiest way to time your run is to execute the following code before each fragment:

then after each fragment place:

The elapsed time is the difference between these two variables.

**Written Problem 3: Give an analysis of the Big-Oh running time for each of the following program fragments:

a)
int sum = 0;
for ( int i = 0; i < 23; i ++)
for ( int j = 0; j < n ; j ++)
sum = sum + 1;

b)
int sum = 0;
for ( int i = 0; i < n ; i ++)
for ( int k = i ; k < n ; k ++)
sum = sum + 1;

c)
public int foo(int n, int k) {
if(n<=k)
return 1;
else
return foo(n/k,k) + 1;
}

Explanation / Answer

These below 3 programs are re-written in java code and used the start and end time to calculate the
the total time of execution is taken.. see the below code and will give the better explanation.

As given in problem. I kept the code between the timers and calculated the elapsed time for execution and printed.

Solution for Question 1:

import java.lang.*;

public class Sample1
{
    public static void main(String[] args)
    {
       int sum = 0,i,j, n=100;
       long start = System.currentTimeMillis();
       for (i = 0; i < 23; i ++)
            for (j = 0; j < n ; j ++)
                sum = sum + 1;
       long end = System.currentTimeMillis();
       System.out.println("Total Time is : " + ((end - start) / 1000));      
    }
}

Solution for Question 2:

import java.lang.*;

public class Sample1
{
    public static void main(String[] args)
    {
       int sum = 0,i,j, n=100;
       long start = System.currentTimeMillis();
       for (i = 0; i < n; i ++)
            for (j = 0; j < n ; j ++)
                sum = sum + 1;
       long end = System.currentTimeMillis();
       System.out.println("Total Time is : " + ((end - start) / 1000));      
    }
}

Solution for Question 3:

import java.lang.*;

public class Sample1
{
   public int foo(int n, int k)
   {
       if(n<=k)
           return 1;
       else
           return foo(n/k,k) + 1;
   }

    public static void main(String[] args)
    {
       int sum = 0,i,j, n=100;
       long start = System.currentTimeMillis();
       sum = new Sample1().foo(100,50);
       long end = System.currentTimeMillis();
       System.out.println("Total Time is : " + ((end - start) / 1000));      
    }
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.