let n=a.length. how many comparisons in algorithm below. public static minMax(co

Question

let n=a.length. how many comparisons in algorithm below.

public static minMax(comparable [] a)

{ if(a.length<1) throw new ILLEGALARGUMENTEXCEPTION("");

minMaxPair p= new MinMaxPair(0,0);

for(int i=1,i<a.length; i++){

if(a[p.min].compareTo(a[i])>0) p.min=i;

if(a[p.max].compareTo(a[i])<0) p.max=i; }

return p; }

---------------------------

whats best and worst case comparisons for algorithm below . what can you say about the performance of algorithm above and below?

public static minMax(comparable [] a)

{ if(a.length<1) throw new ILLEGALARGUMENTEXCEPTION("");

minMaxPair p= new MinMaxPair(0,0);

for(int i=1,i<a.length; i++){

if(a[p.min].compareTo(a[i])>0) p.min=i;

else if(a[p.max].compareTo(a[i])<0) p.max=i;

return p; }

Explanation / Answer

1
let n=a.length. how many comparisons in algorithm below.

public static minMax(comparable [] a)

{ if(a.length<1) throw new ILLEGALARGUMENTEXCEPTION(""); // 1 comparison

minMaxPair p= new MinMaxPair(0,0);

for(int i=1,i<a.length; i++){ // loop run till a.length

if(a[p.min].compareTo(a[i])>0) p.min=i; // a.length comparisons

if(a[p.max].compareTo(a[i])<0) p.max=i; // a.length comparisons
}

return p; }

Total comparisons : (1 + 2*a.length)comparisons

===========================
2
best case : decreasing continuously then only one comparison occurs
worst case : all elements equal or increasing or at-random number
time complexity is @(n) with a.length comparison

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.