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