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.
Answer Posted / 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 |
Post New Answer View All Answers
i don't know about working of nested for loop can any one help me
write a program that can LOCATE and INSERT elements in array using c++ programming languages.
Teta-Omeg-Big-Oh Show that f(n) = n2 + 3n3 is ;(n3).
write a program to calculate the amount of investment after a period n years if the principal investors was p and interest is calculated using compound interest,formular=a=p(1+r)^n
write a program that prompt the user to enter his height and weight,then calculate the body mass index and show the algorithm used
what mean void creat_object?in public class in this code class A{ public: int x; A(){ cout << endl<< "Constructor A";} ~A(){ cout << endl<< "Destructor A, x is\t"<< x;} }; void create_object(); void main() { A a; a.x=10; { A c; c.x=20; } create_object(); } void create_object() { A b; b.x=30; }
How can I Draw an ellipse in 3d space and color it by using graph3d?
write a program using 2 D that searches a number and display the number of items 12 inputs values input 15,20, 13, 30, 38, 40,16, 18, 20 ,18 ,20 enter no. to search : 20
3. Program to find the Sum of give series. a. (1)+(1+2)+(1+2+3)+(1+2+3+4)+……………………………….. b. 1/1+1/9+1/25+1/49+……………...
find level of following tree (state, parent) " J,D I,D H,C E,B F,B G,C B,A D,A C,A A,& K,E L,E L,F M,F N,G O,H P,I P,H Q,I R,J S,K U,P T,L
Performance Algorithm A performs 10n2 basic operations and algorithm B performs 300 lg n basic operations. For what value of n does algorithm B start to show its better performance?
write a function that allocates memory for a single data type passed as a parameter.the function uses the new operator and return a pointer to the allocated memory.the function must catch and handle any exception during allocation
create a stucture student containing field for roll no,class,year and marks.create 10 student annd store them in a file
how to take time as input in the format (12:02:13) from user so that controls remains between these columns?
can you please write a program for deadlock that can detect deadlock and to prevent deadlock.