Week 5 Lab Worksheet CS200 Spring 2015:  Complexity
            ===================================================

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

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

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

	h(x) = x^(n/2) + x^(n/3) + x^(n/4) for some n>=1

	j(x) = x^2 log(x)


Show that g(x) = 19x + x(2x+2) is not O(x)


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: You could put these in an Eclipse project and exercise them.