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.

Perform the functionality of 2-D array through 1-D array and in it the functions to be performed were: (1) Display the array in 2-D format (2) Display a particular element (3) Display a particular row (4) Display a particular column

1 Answers   Nagarro,

readers and writers problem

1 Answers   Cognizant,

What will be the output- for(i=1;i<=3;i++) { printf("%d",i); continue; i++; }

5 Answers   Impetus,

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

0 Answers  

Write a program using two-dimensional arrays that determines the highest and lowest of the 12 input values. Example: Enter 12 numbers: 13 15 20 13 35 40 16 18 20 18 20 14 highest: 40 lowest: 13

1 Answers  

Seat Reservation prog for the theatre. Write a function for seat allocation for the movie tickets. Total no of seats available are 200. 20 in each row. Each row is referred by the Character, "A" for the first row and 'J' for the last. And each seat in a row is represented by the no. 1-20. So seat in diffrent rows would be represented as A1,A2....;B1,B2.....;........J1,J2... Each cell in the table represent either 0 or 1. 0 rep would seat is available , 1 would represent seat is reserved. Booking should start from the last row (J) to the first row(A). At the max 20 seats can be booked at a time. if seats are available, then print all the seat nos like "B2" i.e (2 row, 3 col) otherwise Print "Seats are not available." and we must book consecutive seats only.

1 Answers   Nagarro,

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.

4 Answers  

A string of charaters were given. Find the highest occurance of a character and display that character. eg.: INPUT: AEGBCNAVNEETGUPTAEDAGPE OUTPUT: E

1 Answers  

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?

0 Answers   ASD Lab, Qatar University, UNV,

write a program in c++ to scramble a bmp image file using a scramble key 0x7c and an XOR logic. print out the original image, the scrambled image and the program. Note: the first 24bytes of a bmp file contain the header information of the file.

1 Answers  

write a program that reads a series of strings and prints only those strings begging with letter "b"

0 Answers  

What output does this program generate as shown? Why? class A { A() { cout << "A::A()" << endl; } ~A() { cout << "A::~A()" << endl; throw "A::exception"; } }; class B { B() { cout << "B::B()" << endl; throw "B::exception"; } ~B() { cout << "B::~B()"; } }; int main(int, char**) { try { cout << "Entering try...catch block" << endl; A objectA; B objectB; cout << "Exiting try...catch block" << endl; } catch (char* ex) { cout << ex << endl; } return 0; }

0 Answers