Week 5 Lab Worksheet CS200 Fall 2016:  Complexity
            =================================================
	    

1. What is best (lowest) big-O bound for each of the following functions?

	f(n) = 17 + 3n + 21n^2

	g(n) = 19n + x(2n+2)

	h(n) = n^8 + n^4 + 2^n 

	j(n) = n^2 log(n)


Show that g(n) = n(2n+2) is not O(n)


2. For each of the following methods, determine their best (lowest) worst case
big-O complexity as a function of n:



	public int f0(int n){
		if(n<=1)
			return 1;
		else
			return 1 + f0(n-1) + f0(n-1);
	}


	public int f2(int n){
		int c = 0, step = n;
		while(step>1){
			step/=2;
			c++;
		}
		return c;
	}


	public int f4(int n){
		int c = 0;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for(int k=j;k<n;k++)
					c++;
		return c;
	}


	public int f5(int n){
		int c = 0;
		for(int i=0;i<n;i++){
			int s = n;
			while(s>1){
				s/=2;
				c++;
			}
		}
		return c;
	}



	public int f8(int n){
		int c = 0;
		for(int i=0;i<n;i++)
			for(int j=0;j<=i;j++)
				c++;
		for(int k=0;k<n;k++)
			c++;
		return c;
	}

Hint: Put these in an Eclipse project and exercise them.
      Ask yourself: "what value do these functions return?"