What's running time algorithm?...please help...any idea...thanks.?

Consider the problem of finding the k-th smallest element of a set of n numbers.


Assume that k %26lt;= (n/2).


However, instead of being able to look at the whole date set at once, you are given the numbers one by one in random order. To be precise, the input is a randomly ordered sequence of n numbers x1, x2,..,xn, given one at a time, inserted into a fixed memory cell C. That is, on the i-th input step the contents of xi are placed into C (and the previous contents of C are erased). You can perform any computation between two input steps (including moving the contents of C to a temporary storage location).


a. Suppose that we are interested only in minimizing the amount of storage used by the algorithm.


1. Prove a lower bound that shows any algorithm that finds the k-th smallest number requires k storage cells in addition to C.


2. Give an algorithm that achieves the lower bound you just proved. What is the running time?


b. Now, suppose we want to have a fast running time but still use very little space (though not necessarily the absolute minimum amount of space). Design an O(n) expected time algorithm to find the k-th smallest element using only O(k) storage. You may assume that the value of k is known ahead of time but the value of n is not known until the last element is seen.

What's running time algorithm?...please help...any idea...thanks.?
Ok...this one is a little tricky..but it is basically a variation of a sorting algorthim..to a degree.





bascially the smallest storage we could have is O(k)..think about it...we need to know how to place the values we are getting...and if we get a new value that fits into our storage better, we can boot off the larger of the elements in storage.


Know the question of what the time function is going to be is kind of tricky. specially since we are getting groups of random size as input..this will great effect our time because we are to compare this group with the elements in our storage. Off the top of my head I can't think of a way that you can get O(n) time with this storage...The best you could get..if even possible would be O(nlogn).
Reply:Better you can check this site to get help in Algorithm


http://forums.devshed.com/software-desig...