Author |
Topic: Order of Bucket Sort (Read 592 times) |
|
nks
Junior Member
Gender: 
Posts: 145
|
 |
Order of Bucket Sort
« on: Jan 26th, 2009, 10:53pm » |
 Quote  Modify
|
How the order of bucket sort is O(N+n)?
As it has to sort the element in every bucket is O(Nlog(N)).
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Order of Bucket Sort
« Reply #1 on: Jan 27th, 2009, 2:42am » |
Quote Modify
|
on Jan 26th, 2009, 10:53pm, nks wrote:How the order of bucket sort is O(N+n)?
As it has to sort the element in every bucket is O(Nlog(N)). |
|
But the number of buckets depends on N, the base of the logarithm is N (rather than the usual 2), so you get O(N logN N) = O(n)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
|
Re: Order of Bucket Sort
« Reply #2 on: Jan 28th, 2009, 2:14am » |
Quote Modify
|
Quote:| number of buckets depends on N |
|
That's correct .
It is like
Here n1+n2+n3+.. = N
so
n1log n1 +n1log n1 +..~= N ( it will approach to N)
|
|
IP Logged |
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
|
Re: Order of Bucket Sort
« Reply #3 on: Jan 28th, 2009, 2:15am » |
Quote Modify
|
Corrected !
n1log n1 +n2log n2 +..~= N ( it will approach to N)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print