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
How to swap two ASCII numbers?
A suduco given & u hv 2 check if it is incomplete(blanks left),or correct or incorrect
how to diplay a external image of output on winxp by using c & c++,
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?
1+1/2!+1/3!+...+1/n!
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)
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
write a function that allocates memory for a single data type passed as a parameter.the function uses the new operator and return a pointer to the allocated memory.the function must catch and handle any exception during allocation
Write a C/C++ program that connects to a MySQL server and checks if the InnoDB plug-in is installed on it. If so, your program should print the total number of disk writes by MySQL.
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.)
write a program that reads a series of strings and prints only those strings begging with letter "b"
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 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 Small C++ Class to Transform Any Static Control into a Hyperlink Control?
How can I Draw an ellipse in 3d space and color it by using graph3d?