Assignment: Time complexity

Due Monday, 2/24/03

1. Consider the following method:

   
   public static boolean something( char[] a, char ch )
   {
   	int N = a.length;
   	for( int i=0; i < N; i++ )
   	{
   		if( a[i] == ch )
   			return true;
   	}
   
   	return false;
   }
   

   • What does this method do?
   • If you count =, <, ++, [], and == as operations, how many operations in the best and worst cases are performed when you run this code? (Your answer should be given in terms of N.)

2. Consider the binarySearch method on page 486 of Wu.

   • If I have a sorted array of 10,000 integers and I use binarySearch to search my array for an integer that is not in the array, how many times does the != comparison get performed?
   • If my array has 20,000 integers and I search again for a number that is not in the array, how many times does the != comparison get performed?
   • In the previous problem, I had you count every single operation. This time, I'm only asking you to count the != operation. Why is counting only the != sufficient for predicting the running time behavior of binary search? What single operation could we have counted in the previous problem to determine that algorithm's time behavior?

3. I have an array of integers, and I want to know the distance between the pair of these numbers that are furthest apart. Elmo suggests the following code, which does the job:

   
   public static int elmo( int[] a )
   {
   	int max = 0;
   	for( int i=0; i < a.length; i++ )
   	{
   		for( int j=0; j < a.length; j++ )
   		{
   			if( a[i] - a[j] > max )
   				max = a[i] - a[j];
   		}
   	}
   
   	return max;
   }
   

   • When I used Elmo's code on an array of 2000 integers on my slow old computer at home, it took 7.0 seconds (I tried it several times--7.0 seconds every time). Approximately how long will Elmo's code take to run if N = 6000 (assuming I use the same computer)? Justify your answer. (It is not sufficient to tell me that you ran the code yourself and it took a certain amount of time. I want you to explain why it will take as long as you say it will.)
   • Zoe says she thinks Elmo's code is stupid. Describe an algorithm that will run significantly faster than Elmo's, and explain why it's faster.