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 / 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
| Is This Answer Correct ? | 2 Yes | 1 No |
Post New Answer View All Answers
Code for Easily Using Hash Table?
write a program to calculate the amount of investment after a period n years if the principal investors was p and interest is calculated using compound interest,formular=a=p(1+r)^n
write a program using virtual function to find the transposing of a square matrix?
3. Program to find the Sum of give series. a. (1)+(1+2)+(1+2+3)+(1+2+3+4)+……………………………….. b. 1/1+1/9+1/25+1/49+……………...
Code for Two Classes for Doing Gzip in Memory?
i don't know about working of nested for loop can any one help me
Write a (n) algorithm that sorts n distinct integers, ranging in size between 1 and kn inclusive, where k is a constant positive integer. (Hint: Use a kn-element array.)
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
create a stucture student containing field for roll no,class,year and marks.create 10 student annd store them in a file
write a program that can LOCATE and INSERT elements in array using c++ programming languages.
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; }
1+1/2!+1/3!+...+1/n!
How to swap two ASCII numbers?
Write a simple encryption program using string function which apply the substitution method.
solve the problem in the programming language C++"if a five digit number is input through the keyboard.Write a program to calculate the sum of its digits(hint: use the modulus operator)