Difference between revisions of "Big O Practice Problems"
Line 2: | Line 2: | ||
* State and explain the Big O complexity for each snippet of code. Some may require reductions! | * State and explain the Big O complexity for each snippet of code. Some may require reductions! | ||
− | + | 1) <source lang="java"> | |
//assume myArray contains an array of ints | //assume myArray contains an array of ints | ||
x = 25; | x = 25; |
Revision as of 11:02, 6 January 2009
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; }