Big O Practice Problems

Directions:

• State and explain the Big O complexity for each snippet of code. Some may require reductions!

1)

//assume myArray contains an array of ints
x = 25;
for (int i = 0; i < myArray.length; i++)
{
	if (myArray[i] == x)
		System.out.println("found!");
}

2)

for (int r = 0; r < 10000; r++)
	for (int c = 0; c < 10000; c++)
		if (c % r == 0)
			System.out.println("blah!");

3)

//assume k is unknown
a = 0
for (int i = 0; i < k; i++)
{
	for (int j = 0; j < i; j++)
		a++;
}

4)

int key = 0;	//key may be any value
int first = 0;
int last = intArray.length-1;;
int mid = 0;
boolean found = false;
		
while( (!found) && (first <= last) )
{
	mid = (first + last) / 2;
								
	if(key == intArray[mid]) 
		found = true;
	if(key < intArray[mid])
		last = mid - 1;
	if(key > intArray[mid]) 
		first = mid + 1;
}

5)

int currentMinIndex = 0;

for (int front = 0; front < intArray.length; front++)
{
	currentMinIndex = front;
	
	for (int i = front; i < intArray.length; i++)
	{
		if (intArray[i] < intArray[currentMinIndex])
		{
			currentMinIndex = i;
		}
	}
	
	int tmp = intArray[front];
	intArray[front] = intArray[currentMinIndex];
	intArray[currentMinIndex] = tmp;
}