Help with complexity classes and running time

[flyingcurry]

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);
		}
	}

}

[tong1]

I have questions for you.
(1) Where is the definition of the class Console? As fas as I know it is a defined class in the package: java.io
(2) For line 15: in the class Graphics there is a member method drawRect(int x, int y, int width, int length), but in your code the handle is Console's instance. Where is the definition of its method?

[flyingcurry]

I have questions for you.
(1) Where is the definition of the class Console? As fas as I know it is a defined class in the package: java.io
(2) For line 15: in the class Graphics there is a member method drawRect(int x, int y, int width, int length), but in your code the handle is Console's instance. Where is the definition of its method?

I left that part out because it contained other personal information, here

import hsa_ufa.Console;

/**
 * A template for generating timing data for a method. This program
 * takes multiple runs for each n value and averages them to give you
 * cleaner data.
 *
 * The output of this program can be cut and paste into Excel to graph it.
 *
 * October 1, 2010. Modified September 13, 2010. Modified September 21, 2010.
 *
 * @author
 **/
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);
		}
	}

}

[tong1]

Based on your description I would assume that the method drawRect(int x0,int y0,int width, int length) has a time complxity O(n) since the plot shows

"an increasing linear trend at first".

The method must limit the width and length, that is, if either the width or the length reaches the maximum value (upper limit) it will remain unchanged. That's why

"the plot finally remains constant...".

The plot shows an real observation.

" then decrease rapidly"

may be due to some optimization of the operation when it is feasible.