• Post Reply Bookmark Topic Watch Topic
  • New Topic

Algorithm Efficiency and sorting question.  RSS feed

 
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Steve. I appreciate your help on the matter.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!