Author |
Topic: nth order statistics where n is power of 2 (Read 1398 times) |
|
singhar
Newbie
Posts: 22
|
 |
nth order statistics where n is power of 2
« on: Mar 21st, 2010, 9:21am » |
 Quote  Modify
|
We know that sorting is O(nlogn). But is it possible to find the kth order statistics of an unsorted array faster than O(nlogn) given the fact that k is a power of 2. So we are looking for the 1st, 2nd, 4th, 8th, 16th, ... smallest numbers here.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: nth order statistics where n is power of 2
« Reply #1 on: Mar 21st, 2010, 9:54am » |
Quote Modify
|
It doesn't matter whether k is a power of 2, you can do it in O(n) time regardless.
When you pick a pivot, you only need to work on with one of the two halves of the array. You can use median of medians to choose a good pivot which guarantees O(n) runtime (choosing a pivot randomly only gives O(n) on average)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
mmgc
Newbie
Gender:
Posts: 47
|
|
Re: nth order statistics where n is power of 2
« Reply #2 on: Mar 22nd, 2010, 1:39am » |
Quote Modify
|
We can traverse the array once and figure out the nth smallest element.Just need to keep track of nth smallest element.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: nth order statistics where n is power of 2
« Reply #3 on: Mar 22nd, 2010, 3:51am » |
Quote Modify
|
on Mar 22nd, 2010, 1:39am, mmgc wrote:| We can traverse the array once and figure out the nth smallest element.Just need to keep track of nth smallest element. |
|
And how exactly are you going to do that?
If you, say, keep a maxheap of size K (where you replace the max by the current element if the latter is smaller), you'll still take O(N log K) time to find the Kth smallest element.
How do you plan to keep track of the Kth smallest element in O(1) time per step?
|
| « Last Edit: Mar 22nd, 2010, 3:58am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
singhar
Newbie
Posts: 22
|
|
Re: nth order statistics where n is power of 2
« Reply #4 on: Mar 22nd, 2010, 10:43am » |
Quote Modify
|
@ towr, you mean we can find all the kth order statistics in O(n) or just any one of them? I am looking for all the kth order statistics where k is a power of 2. In other words, it is almost asking for sorting the array, but doesn't care about the elements whose rank is not a power of 2.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: nth order statistics where n is power of 2
« Reply #5 on: Mar 22nd, 2010, 11:22am » |
Quote Modify
|
Ah, I was thinking we only needed to find one.
But I think if you want every 2kth statistic, you can use the same approach. If you split an array in two, then the last half will only contain one of them; and we can find any single kth statistic in O(n) time, so it should only take about twice as long to find all as finding just one.
|
| « Last Edit: Mar 22nd, 2010, 11:22am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
singhar
Newbie
Posts: 22
|
|
Re: nth order statistics where n is power of 2
« Reply #6 on: Mar 22nd, 2010, 2:14pm » |
Quote Modify
|
But I think you are still right, the time complexity is still O(n) even if we are computing all the kth order statistics where k is a power of 2:
T(n) = C * n * (1 + 1/2 + 1/4 + .. + 1/(2^k))
= C * n * ( 2 * (1 - 1/(2 ^ (k+1)))
= C * n * ( 2 * (1 - 1 / 2n))
= C * n * ( 2 * (2n - 1) / 2*n)
= C * (2n - 1) = O(n)
n is given / guranteed to be a power of 2 here.
|
|
IP Logged |
|
|
|
mmgc
Newbie
Gender:
Posts: 47
|
|
Re: nth order statistics where n is power of 2
« Reply #7 on: Mar 22nd, 2010, 9:40pm » |
Quote Modify
|
on Mar 22nd, 2010, 3:51am, towr wrote:
And how exactly are you going to do that?
If you, say, keep a maxheap of size K (where you replace the max by the current element if the latter is smaller), you'll still take O(N log K) time to find the Kth smallest element.
How do you plan to keep track of the Kth smallest element in O(1) time per step? |
|
I completely missed the complexity involved...thanks for making me think again..
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print