Show that the select algorithm below has worst case complexity of O(n 2 ). (It i
ID: 3684529 • Letter: S
Question
Show that the select algorithm below has worst case complexity of O(n2).
(It is possible to modify the algorithm so the worst case complexity is only O(n).
select(A, p, r, i) {
if (p == r) { // if array has only 1 element
return A[p]
}
q = partition(A, p, r) // get the position of the pivot bet. p and r
k = q –p + 1 // rank relative to p
if (i== k) {
return A[q]
} else if(i< k) {
return select(A, p, q-1, i) // search in first part
} else {
return select(A, q+1, r, i-k) // search in second part
}
}
Explanation / Answer
The algorithm is written as a java code and the start and end time tested to prove the time complexity performance
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package pivotselecttimecomplexityfinding1;
import java.util.*; // includes Random
import java.io.*;
import java.util.Collections;
import java.util.Arrays;
//import static pivotselecttimecomplexityfinding1.PivotSelectTimeComplexityFinding1.select;
/**
*
* @author Admin
*/
public class PivotSelectTimeComplexityFinding1 {
public static select partition(int [] Array, int front, int rear) {
int q, k, j, i = 0;
k = q-front + 1;
if ( i == k) return Array[q];
else if ( i < k) {
return ( select(Array, front, q-1, i) );
else
return ( select (Array, q+1, rear, i-k));
}
} // end func partion
/**
* @param Array
* @param front
* @param rear
* @param i
* @param args the command line arguments
*/
public static void select(int[] Array, int front, int rear, int i ) {
if ( front == rear) return Array[front];
} // end select function
public static void main(String[] args) {
// TODO code application logic here
int [] Array = new int[100];
int front = 0, rear = 0, i = 0;
long startTimeMS = System.currentTimeMillis();
long startTimeNS = System.nanoTime();
long stopTimeMS, stopTimeNS;
// implement the algorithm for select as given in the question:
select(Array,front ,rear,i);
stopTimeMS = System.currentTimeMillis();
stopTimeNS = System.nanoTime();
System.out.println("Time taken = " + (stopTimeMS - startTimeMS) + " Miili seconds");
} // end main
} // end public class
The array size can be changed from 100 to 500,000 and then to a million and the out put can be seen in milli seconds for the time taken - that will show that the algorithm has the worst complexity of Order of n square = O(n^2)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.