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

Code for Small C++ Class to Transform Any Static Control into a Hyperlink Control?

3058

---

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

3457

---

Write a simple encryption program using string function which apply the substitution method.

6120

---

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?

7834

---

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

2274

---

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

5118

---

Question 1: Implement a base class Appointment and derived classes Onetime, Daily, Weekly, and Monthly. An appointment has a description (for example, “see the dentist”) and a date and time. Write a virtual function occurs_on(int year, int month, int day) that checks whether the appointment occurs on that date. For example, for a monthly appointment, you must check whether the day of the month matches. Then fill a vector of Appointment* with a mixture of appointments. Have the user enter a date and print out all appointments that happen on that date. *This Should Be Done IN C++

1167

---

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

2463

---

Teta-Omeg-Big-Oh Show that f(n) = n2 + 3n3 is ;(n3).

3629

---

A suduco given & u hv 2 check if it is incomplete(blanks left),or correct or incorrect

2885

---

Code for Easily Using Hash Table?

3034

---

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.

2716

---

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

3064

---

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

7686

---

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

3120

---