best case and worst case running time. Big O?

  • Thread starter Thread starter isaa i
  • Start date Start date
I

isaa i

Guest
can you say if i am correct with the following and if not help me get on the right track. i need to find the best and worst running time if they are different.

a)
void sort(double[] array)
{
for (int i = array.length - 1 ; i > 0 ; i--) {
for (int j = 0 ; j < i ; j++) {
if (array[j] > array[j+1]) {
double temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}


let n=array.length -1
the outer loop executes n times. and for each i'th iteration of the outer loop, the inner loop runs n - i times. so in the worst case all the statements inside the inner loop which each take O(1) time will get executed for a total of 1 + 2 + ... + n times which is equivalent to (n(n+1))/2 times
keeping the highest order term and dropping the constants, we will get O(n^2) as the worst case for this part.
The best case happens when the array is already sorted but in that case we are still making n(n+1)/2 comparisons so the best case is still O(n^2)

b)
boolean containSameNumbers(double[] array1, double[] array2)
{
if (array1.length != array2.length) {
return false;
}

selectionSort(array1); // assume normal selection sort implementation
selectionSort(array2);

for (int i = 0 ; i < array1.length ; i++) {
if (array1 != array2) {
return false;
}
}

return true;
}

The best case here is when the two array don't have the same length and it only takes constant time or O(1) to end the function after checking for this condition and returning false.
if the lengths for two arrays are the same, two selection sorts take place which takes O(n^2) + O(n^2) or simply O(n^2)
where n = array1.length = array2.length . then we have a loop which makes n comparisons in its worst case, and only 1 in
its best case. However since with each call to this function we still have the calls to selection sort , the order of n^2
dominates and therefore we will get O(n^2) as the running time of this function for both best and worst cases.

c)
void sort(double[] array)
{
boolean ok = true;
for (int i = 0 ; i < array.length-1 ; i++)
{
if (array > array[i+1])
{
ok = false;
}
}

if (ok)
{
return;
}

selectionSort(array); // assume normal selection sort implementation
}

Here the first loop runs n - 1 times where n = array.length . then we have a selectionSort
which takes O(n^2) . so the running time for the function will be O(n^2 + n) = O(n^2) for all cases.


d)
void sumRows(double[][] array)
{
for (int r = 0 ; r < array.length ; r++)
{
array[r][array[r].length-1] = 0.0;
for (int c = 0 ; c < array[r].length-1 ; c++)
{
//array[r][array[r].length-1] += array[r][c];
array[r][array[r].length-1] = array[r][array[r].length-1] + array[r][c];
}
}
}


since Java's 2D arrays can have rows with different lengths, here we cannot simply use the usual method we use for standard nested loops in which we use the loops' bounds to determine the running time. The simple way to get the running time of this loop is to notice that
this method operates on all of the elements of the passes 2D array. so if n is the total number of elements in the passed 2D array, this function will be O(n) or will be a linear time function.


e)
int findEmptyRow(double[][] array)
{
for (int r = 0 ; r < array.length ; r++)
{
boolean found = true;
for (int c = 0 ; c < array[r].length ; c++)
{
if (array[r][c] != 0.0)
{
found = false;
break;
}
}
if (found)
{
return r;
}
}

return -1;
}

no idea with this one, please help.
 
Back
Top