For homework, we have to find the time complexity class of certain algorithms and explain why it has that certain complexity class.
So, I have a couple of questions:
- Why is the first running time always so much longer than the ones after? (setting up the application or something??)
- What is the complexity class of an algorithm that draws a square of side length n, like this one:
c.drawRect(0,0,n,n);
why is it that way?
- What is the complexity class of an algorithm that draws a circle of diameter n, like this:
c.drawOval(0, 0, n, n);
why is it that way?
I'm asking these questions because after I graphed the n vs. running time scatter plots, the time complexity seems to be randomly changing. E.g. the square drawing algorithm would have an increasing linear trend at first, then decrease rapidly, then remain constant...??Why is this??? :o
Thanks.
--------------------
Below is the snippet of some code from the square drawing algorithm, just in case my questions aren't making much sense.
public class SquareTime {
static Console c= new Console();
/**
* Sample method to time.
*
* Finds whether a given number is prime.
*
* @param n the number to test
* @return true if n is prime, false otherwise
**/
public static boolean drawSquare(int n)
{
c.drawRect(0,0,n,n);
return true;
}
public static void main(String[] args)throws InterruptedException
{
// ***********************************************
// CHANGE THESE CONSTANTS TO CONFIGURE YOUR RUN
final int MIN_N = 1; // starting value for n
final int MAX_N = 2000; // ending value for n
final int INC_N = 1; // n increment
final long NUM_ITERATIONS = 1000; // number of runs to average over for each n value
// ***********************************************
// *********************************
// PUT ONE TIME ONLY SETUP CODE HERE
// e.g. creating an hsa_ufa console
//
// Console c = new Console();
// *********************************
// this loop times the count method for n=10, 20, 30, etc...
for(int n=MIN_N; n<=MAX_N; n+=INC_N)
{
long totalTime = 0;
for (int i=0; i<NUM_ITERATIONS; i++)
{
// **********************************
// PUT ANY REPEATED SETUP CODE YOU NEED HERE
// e.g. creating/initializing arrays
//
// **********************************
long startTime = System.nanoTime(); // get start time in nanoseconds
// ***************************************
// PUT THE CODE YOU WANT TO TIME HERE
// usually just a call to the method you are timing
//
drawSquare(n);
// drawLine(n,c);
//
// ***************************************
long endTime = System.nanoTime(); // get end time in nanoseconds
totalTime += endTime - startTime; // add up the total time taken
}
long averageTime = totalTime / NUM_ITERATIONS; // compute and display the average running time
System.out.println(n+"\t"+averageTime);
}
}
}