programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Algorithm Efficiency and sorting question.

Greenhorn
Posts: 11
I am needing someone to give me a hint...steer me in the right direction as to how I should approach this problem. The key, I'm thinking, is obtaining some value for n. With such a value I should be able to solve the problem. Any thoughts? Suggestions. Thanks in advance.

Consider the following Java method f. Do not be concerned with f's purpose. How many comparisons does f perform?
===========================================================================
public static void f(int[] theArray, int n)
{
int temp;
for (int j = 0; j < n; ++j)
{
int i = 0;
while(i<=j)
{
if(theArray[i] < (theArray[j]))
{
temp = theArray[i];
theArray[i] = theArray[j];
theArray[j] = temp;
} //end if
++i;
} //end while
} //end for
} //end f

Ranch Hand
Posts: 35
Hi,

The inner while loop executes j times on each iteration. The value of j varies from 1 to n in the for loop. Thus, number of comparisons done by f = 0 + 1 + 2 +....+n = n(n+1)/2 which is O(n^2)

_steve.

Luke Forga
Greenhorn
Posts: 11
Thanks Steve. I appreciate your help on the matter.

 Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters?