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.

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

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

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

Answer / rajashree

3n/2-2

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. }

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();

}

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

Answer / harish

2(n-1)

Answer / jeya

in tree the left most elemt is minimum element.the right
most element is max element.

1. Write a program using one dimensional array that calculates the sum and average of the five input values from the keyboard and prints the calculated sum and average.

2 Answers  

how to write a program that opens a file and display in reverse order?

0 Answers   SMC,

Display Pattern: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 &#8230;

2 Answers   Mind Tree,

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

0 Answers  

Write a C/C++ program that connects to a MySQL server and checks if the InnoDB plug-in is installed on it. If so, your program should print the total number of disk writes by MySQL.

0 Answers  

write a function – oriented program that calculates the sum of the squares from 1 to n. thus, if the input is 3, the output is 14

3 Answers  

Complexity T(n) Write a linear-time algorithm that sorts n distinct integers, each of which is between 1 and 500. Hint: Use a 500-element array. (Linear-time means your algorithm runs in time c*n + b, where c and b are any constants that do not depend on n. For example, your algorithm can run in time n, or time 2n + 1, or time 5n + 10, or time 100n + 6, but not time c*n*n = c*n?.)

1 Answers   Qatar University,

How do I store linked list datas into an array?

1 Answers  

Assume in University Every student in university as entity, prepare a class for student that store the roll no, name, dob of student, and make funtion of deletion, manipulation, addition of student record.

0 Answers  

Code for Method of Handling Factorials of Any Size?

0 Answers  

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

0 Answers   HCL,

how to find out the maximum number out of the three inputs.

6 Answers   ABC, Apple, C3I, HP, TCS,