Big O Practice Problems - Revision history

Admin at 15:03, 6 January 2009

2009-01-06T15:03:22Z

Admin at 15:02, 6 January 2009

2009-01-06T15:02:14Z

Admin at 15:01, 6 January 2009

2009-01-06T15:01:43Z

Admin: New page:

 Directions: Save this file locally and edit it directly.  State and explain the Big O complexity for each snippet of code.  Some may require reductions!  1)  //assume myArray contain...

2009-01-06T15:00:24Z

New page: <pre> Directions: Save this file locally and edit it directly. State and explain the Big O complexity for each snippet of code. Some may require reductions! 1) //assume myArray contain...

New page

<pre>
Directions: Save this file locally and edit it directly. 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;
}

</pre>

@@ Line 2: / Line 2: @@
 * State and explain the Big O complexity for each snippet of code.  Some may require reductions!
-) <source lang="java">
+)
 //assume myArray contains an array of ints
 x = 25;
@@ Line 11: / Line 13: @@
+}
 </source>
 )
 for (int r = 0; r < 10000; r++)
 	for (int c = 0; c < 10000; c++)
 		if (c % r == 0)
 			System.out.println("blah!");
+</source>
 )
 //assume k is unknown
 a = 0
@@ Line 32: / Line 33: @@
 		a++;
+}
+</source>
 )
 int key = 0;	//key may be any value
 int first = 0;
@@ Line 55: / Line 55: @@
 		first = mid + 1;
+}
+</source>
 )
+<source lang="java">
 int currentMinIndex = 0;
@@ Line 80: / Line 78: @@
 	intArray[currentMinIndex] = tmp;
+}
+</source>

@@ Line 2: / Line 2: @@
 * State and explain the Big O complexity for each snippet of code.  Some may require reductions!
-# <source lang="java">
+) <source lang="java">
 //assume myArray contains an array of ints
 x = 25;

@@ Line 1: / Line 1: @@
-<pre>
+'''Directions:'''
-Directions: Save this file locally and edit it directly.  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!
 //assume myArray contains an array of ints
 x = 25;
@@ Line 11: / Line 10: @@
 		System.out.println("found!");
+}
+</source>