We are given n keys and an integer k such that 1<=k<=n.Give an efficient algo to find any one of the k smallest keys .

Question

How many key comparisons are there , what is the lower bound and upper bound ?

 

For calculating the lower bound , should we consider the case when the keys are all in non-increasing fashion and then after n-k comparisons we shall find one of the K keys and then we are done , and for calculating upper bound then , what should be the case considered for the order of keys ?

Answer 1

I suppose here the upper bound and lower bound cases would be same.
To find one of the k smallest keys, we need to look at n-k+1 elements atleast to be sure that we have chosen one among k smallest keys.. So, total n-k comparisons
In the question nothing about the order of the keys is mentioned. so we must look for n-k+1 elements, so n-k comparisons.
Time complexity should be ϴ(n-k).

Comments

Well, i dont think it is possible to do that in O(n) time.
1. The sorting you are talking about has a best case of Ω(n), and we cannot say whether a given array is a best case or not directly. In the worst case of say radix sort or hash table/etc the worst case can become O(n²).
So, saying that it will take O(n) time is clearly not correct.
2. In doubly and circular linked list, the access time of any element is not O(1). 
Suppose we want to access the n/2th element, we need to either start from head or tail(which is same for circular list) and need to parse through n/2 elements in the list.. which is O(n).
But then to first sort it using your method, we may require O(n²) time..

---

ok ,getting ur view So, if we have to select an sorting between (a) Insertion sort and (B) Merge sort for this algo We will select Merge sort. right? As in insertion sort worst and avg case has a possibility to get complexity O(n^2). Right?

Best case and Worst case can predict only after operation is performed. right?

and if we have to select between (A)Insertion Sort and (B) Quick sort ?

then we can select Insertion sort, as quick sort worst case also gives O(n^2). right?

---

Your first two points are right.. thats exatly what i wanted to say :)

But the last one isnt.
Now in quick sort, the worst case occurs fairly very less number of times (assuming equal probability for each permutation)
And i dont remember the exact analysis now, but its given in Cormen..
Although the worst case time of quick sort is O(n²), the EXPECTED time for it is still nlogn..the probability of worst case can even be lowered more by using the randomized version of quick sort.

So, to answer your last question, if nothing is mentioned about the input we should choose quicksort(asymptotically better) because it has less expected running time..
But suppose, if we are given the numbers in array are nearly sorted, then we can choose insertion sort as it will produce better results for such cases, close to Θ(n) time..