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 / 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
Is This Answer Correct ? | 29 Yes | 4 No |
Post New Answer View All Answers
write a program that prompt the user to enter his height and weight,then calculate the body mass index and show the algorithm used
how to take time as input in the format (12:02:13) from user so that controls remains between these columns?
How to swap two ASCII numbers?
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?
write a program that reads a series of strings and prints only those strings begging with letter "b"
i don't know about working of nested for loop can any one help me
Write a simple encryption program using string function which apply the substitution method.
write a program using virtual function to find the transposing of a square matrix?
write a program that creates a sequenced array of numbers starting with 1 and alternately add 1 and then 2 to create the text number in the series , as shown below. 1,33,4,6,7,9,............147,148,150 Then , using a binary search , searches the array 100 times using randomly generated targets in the range of 1 to 150
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; }
how to write a program that opens a file and display in reverse order?
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
How can I Draw an ellipse in 3d space and color it by using graph3d?
Create a program to read two random data set in two files named data1.txt and data2.txt manifold contains integer numbers, whereas data2.txt file contains the float type numbers. Simpanlahmasing each into 2 pieces of data that is an array of type integer array and an array of type float, then calculate the average numbers in the second array.
Code for Method of Handling Factorials of Any Size?