Answer Posted / 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

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

3068

---

write a program that reverses the input number of n.Formulate an equation to come up with the answer.

7634

---

develop a program to calculate and print body mass index for 200 employees

2613

---

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

2413

---

how to take time as input in the format (12:02:13) from user so that controls remains between these columns?

2223

---

write a program that prompt the user to enter his height and weight,then calculate the body mass index and show the algorithm used

4815

---

create a stucture student containing field for roll no,class,year and marks.create 10 student annd store them in a file

2673

---

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

2528

---

Write a C/C++ program that connects to a MySQL server and displays the global TIMEZONE.

5052

---

write a function that reverse the elements of an array in place.The function must accept only one pointer value and return void.

4515

---

how to diplay a external image of output on winxp by using c & c++,

3400

---

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.

2644

---

Definition of priority queue was given. We have to implement the priority queue using array of pointers with the priorities given in the range 1..n. The array could be accessed using the variable top. The list corresponding to the array elements contains the items having the priority as the array index. Adding an item would require changing the value of top if it has higher priority than top. Extracting an item would require deleting the first element from the corresponding queue. The following class was given: class PriorityQueue { int *Data[100]; int top; public: void put(int item, int priority); // inserts the item with the given priority. int get(int priority); // extract the element with the given priority. int count(); // returns the total elements in the priority queue. int isEmpty(); // check whether the priority queue is empty or not. }; We had to implement all these class functions.

4894

---

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?

3313

---

Given a table of the form: Product Sold on A 1/1/1980 B 1/1/1980 C 1/1/1980 A 1/1/1980 B 1/1/1980 C 2/1/1980 A 2/1/1980 There are 30 products and 10,000 records of such type. Also the month period during which sales happened is given to u. Write the program to display the result as: Product Month No. of copies A January 12 A February 15 A March 27 B January 54 B February 15 B March 10 C January 37

2476

---