Interested to Buy Any Domain ? << Click Here >> for more details...
Min-Max
Write an algorithm that finds both the smallest and
largest numbers in a list of n numbers and with complexity
T(n) is at most about (1.5)n comparisons.
- 10 Answers
- 46765 Views
- ABC, College School Exams Tests, ITC Infotech, Kyambogo University, Qatar University, I also Faced
- E-Mail Answers
Answers were Sorted based on User's Feedback
Answer / oracle
Simple, first compare all elements pairwise, total n/2
comparisons. Then, you got two sets, first set has all
greater elements, and second all smaller ones. Find largest
in the first set (n/2) and smallest in the second set
(n/2). You got both largest and smallest ones, in total n/2
+ n/2 + n/2 = 3n/2 comparisons.
| Is This Answer Correct ? | 54 Yes | 11 No |
Answer / ashekur rahman
Time Complexity T(n) <= 3n/2
Proof:
We will calculate comparison in three steps.
1) compare pairwise will divide two sub array.
2) linear search of first sub array
3) linear search of second sub array
For even number of elements,
step 1 needs n/2 comparisons where both sub array contains
n/2 number of elements. Step 2 or 3 needs (n/2 - 1)
comparisons by linear search.
T(n) = n/2 + 2(n/2 - 1)
= 3n/2 - 1
Again,
For odd number of elements,
step 1 needs (n/2 + 1) comparison.
Now if first sub array contains n/2 number of elements then
second sub array contains (n/2 + 1) number of elements
or if first sub array contains (n/2 + 1) number of elements
then second sub array contains n/2 number of elements
Therefore,
T(n) = (n/2 + 1) + (n/2 + 1 - 1) + (n/2 - 1)
= 3n/2
So, T(n) = 3n/2 - 1, if n is even number
and T(n) = 3n/2, if n is odd number
| Is This Answer Correct ? | 29 Yes | 4 No |
Answer / ashekur rahman
Please follow the link below again, where I have written a
complete C# program. Where I printed the time complexity also.
http://ashikmunna.blogspot.com/2009/05/write-algorithm-that-finds-both_28.html
| Is This Answer Correct ? | 13 Yes | 1 No |
Answer / ashekur rahman
http://ashikmunna.blogspot.com/2009/05/write-algorithm-that-finds-both.html
Please follow the link to see the answer. Where I
implemented the algorithm and also calculated the time
complexity.
Thanks.
- Ashekur Rahman
| Is This Answer Correct ? | 11 Yes | 1 No |
Answer / kush singh
1. Algorithm MaxMin (i,j, max, min)
2. // a[1:n] is a global array Parameter i and j are integers,
3. // 1 „T i „T j < n. The effect is to set max and min to the
4. // largest and smallest values in a [i, j], respectively.
5. {
6. if (i=j) then max:=min:=a[i]; //small(P)
7. else if (i = j ¡V 1) then //Another case of Small (P)
8. {
9. if a [i] < a[j] then
10. {
11. max:=a[j]; min:=a[i];
12. }
13. else
14. {
15. max:=a[i]; min:=a[j]
16. }
17. }
18. else
19. {
20. // If P is not small, divide P into subproblems
21. // Find where to split the set
22. mid:= „¾(i+j)/2„Î;
23. //Solve the subproblems
24. Maxmin (i, mid, max, min);
25. MaxMin (mid+i, j, max1, min1);
26. // Combine the solutions
27. if (max<max 1) then max:=max1;
28. if(min>min1) then min:=min1;
29. }
30. }
| Is This Answer Correct ? | 4 Yes | 0 No |
Answer / srinivasan
#include<stdio.h>
#define size 10
void main()
{
int a[size]={5,3,18,7,20,0,2,1,16,13},i,j,count=0,t,max,min;
clrscr();
for(i=0;i<size;i++)
printf("%5d",a[i]);
for(i=0,j=size-1;i<j;i++,j--)
{
count++;
if(a[i]>a[j])
{
t=a[i],a[i]=a[j],a[j]=t;
}
}
printf("\n\n");
for(i=0;i<size;i++)
printf("%5d",a[i]);
printf("\n\n");
min=a[0];
for(i=1;i<size/2;i++)
{
count++;
if(a[i]<min)
min=a[i];
}
max=a[size/2];
for(j=size/2+1;j<size;j++)
{ count++;
if(a[j]>max)
max=a[j];
}
printf("%d\n%d is max,min",max,min);
printf("\n%d\n",count);
getch();
}
| Is This Answer Correct ? | 10 Yes | 9 No |
Answer / amirhosain shahsavari
hi
Some of notations in answer 5 is absolutely wrong:
for even number n: T(n)=(3/2)n-2
for odd number n: we ignore the last item of array.Now you
can find Min1 (minimum of the array items ignoring the last
item), Max1 (maximum of the array items ignoring the last
item) (notice that n-1 is even so Min1 and Max1 can be found
at (3/2)(n-1)-2 comparisons). After that you should compare
Min1 and Max1 with the last item (that you ignored in the
first step). so you need at most (3/2)(n-1)-2+2=(3/2)n-(3/2)
comparisons to find the entire array items
| Is This Answer Correct ? | 2 Yes | 1 No |
Answer / jeya
in tree the left most elemt is minimum element.the right
most element is max element.
| Is This Answer Correct ? | 4 Yes | 7 No |
write a proram using exceptional handling create a error & display the message "THERE IS AN ERROR?... PLEASE RECTIFY"?
write a program to calculate the radius for a quadratic equation use modular programming(function abitraction)hint use quadratic function
1 Answers ICAN, Jomo Kenyatta University,
i don't know about working of nested for loop can any one help me
program to find the magic square using array
What output does the following code generate? Why? What output does it generate if you make A::Foo() a pure virtual function? class A { A() { this->Foo(); } virtual void Foo() { cout << "A::Foo()" << endl; } }; class B : public A { B() { this->Foo(); } virtual void Foo() { cout << "A::Foo()" << endl; } }; int main(int, char**) { A objectA; B objectB; return 0; }
write a program that can LOCATE and INSERT elements in array using c++ programming languages.
1. Write a program that performs the following. The user inputs a number and then enters a series of numbers from 1 to that number. Your program should determine which number (or numbers) is missing or duplicated in the series, if any. For example, if the user entered 5 as the initial number and then entered the following sequences, the results should be as shown. Input Sequence Output ---------------------- --------------- 1 2 3 4 5 Nothing bad However, if 7 were the high number, the user would see the results on the right for the following number entries: Input Sequence Output ---------------------- --------------- 1 3 2 4 5 Missing 6 Missing 7 And if 10 were the high number and the user entered the numbers shown on the left, note the list of missing and duplicate numbers: Input Sequence Output ---------------------- --------------- 1 2 4 7 4 4 5 10 8 2 6 Duplicate 2 ( 2 times) Missing 3 Duplicate 4 ( 3 times ) Missing 9
i really need help about this.. write a program to display the set of odd and even numbers separately. find the highest and lowest value of the given numbers.
what is the diffrence between ++x , x++ pleaaaaase ???
Write a program that print in screen a tree with its height taken from user by entering number of 4 digits and find the odd numbers then calculate the sum of odd numbers so he get the height of tree?
how to take time as input in the format (12:02:13) from user so that controls remains between these columns?
Counting in Lojban, an artificial language developed over the last fourty years, is easier than in most languages The numbers from zero to nine are: 0 no 1 pa 2 re 3 ci 4 vo 5 mk 6 xa 7 ze 8 bi 9 so Larger numbers are created by gluing the digit togather. For Examle 123 is pareci Write a program that reads in a lojban string(representing a no less than or equal to 1,000,000) and output it in numbers.
C Code 
