Difference between revisions of "Big O Practice Problems"
From WLCS
| 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"> | + | 1) |
| + | |||
| + | <source lang="java"> | ||
//assume myArray contains an array of ints | //assume myArray contains an array of ints | ||
x = 25; | x = 25; | ||
| Line 11: | Line 13: | ||
} | } | ||
</source> | </source> | ||
| − | |||
| − | |||
2) | 2) | ||
| + | <source lang="java"> | ||
for (int r = 0; r < 10000; r++) | for (int r = 0; r < 10000; r++) | ||
for (int c = 0; c < 10000; c++) | for (int c = 0; c < 10000; c++) | ||
if (c % r == 0) | if (c % r == 0) | ||
System.out.println("blah!"); | System.out.println("blah!"); | ||
| − | + | </source> | |
| − | |||
3) | 3) | ||
| + | <source lang="java"> | ||
//assume k is unknown | //assume k is unknown | ||
a = 0 | a = 0 | ||
| Line 32: | Line 33: | ||
a++; | a++; | ||
} | } | ||
| − | + | </source> | |
| − | |||
| − | |||
4) | 4) | ||
| + | <source lang="java"> | ||
int key = 0; //key may be any value | int key = 0; //key may be any value | ||
int first = 0; | int first = 0; | ||
| Line 55: | Line 55: | ||
first = mid + 1; | first = mid + 1; | ||
} | } | ||
| − | + | </source> | |
| − | |||
| − | |||
5) | 5) | ||
| − | + | <source lang="java"> | |
int currentMinIndex = 0; | int currentMinIndex = 0; | ||
| Line 80: | Line 78: | ||
intArray[currentMinIndex] = tmp; | intArray[currentMinIndex] = tmp; | ||
} | } | ||
| − | + | </source> | |
| − | </ | ||
Latest revision as of 11:03, 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;
}
