Meaningless Drivel is fun!*
The moose likes Performance and the fly likes sorting performance - need help with math Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Performance
Bookmark "sorting performance - need help with math" Watch "sorting performance - need help with math" New topic
Author

sorting performance - need help with math

Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

im doing research on sorting algorithms. i have 2 articles about radix sort. one says radix sort is O(n), in other words linear. the other says it is only linear if the wordsize of the computer(32 or 64 nowadays) is >= log n, otherwize it its O(n log n). isnt log 1,000,000 only 6?
even if they mean log base 2, 2^32 is a huge number
ps: the second article introduces an algorithm with O(n log log n)
[ April 18, 2004: Message edited by: Randall Twede ]

SCJP
Visit my download page
Warren Dew
blacksmith
Ranch Hand

Joined: Mar 04, 2004
Posts: 1332
    
    2
Originally posted by Randall Twede:
even if they mean log base 2, 2^32 is a huge number

About 4 Billion, in fact.
However, some people deal with data sets larger than that.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

ok, so for normal folks it would be linear. i get the idea though.
im really getting into this research, it's cool!
i should have known it was base 2 but i think in my paper i use subscript to make it clear
[ April 18, 2004: Message edited by: Randall Twede ]
Dirk Schreckmann
Sheriff

Joined: Dec 10, 2001
Posts: 7023
Side note, lg is a common representation for log base 2.


[How To Ask Good Questions] [JavaRanch FAQ Wiki] [JavaRanch Radio]
Jeroen Wenting
Ranch Hand

Joined: Oct 12, 2000
Posts: 5093
another note: log is used to mean base 2 in all applications except computing (for some reason) unless a base is specified.
log base e is generally written as ln.
So possibly the authors meant log base 2.


42
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
Um, in applications outside computing, log usually means base 10. In my experience at least. Perhaps it's different in Europe? I doubt it - outside of computing, base 2 just isn't as useful to most people as base 10 is. Errr, was. The main motivation for using logs was as a faster replacement for multiplication, back in the dark ages before calculators and computers. This is easiest if you use logs base 10, to match our number system.


"I'm not back." - Bill Harding, Twister
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11256
    
  16

As a former math teacher, log always meant base 10. And Jim, it still is quite relevant - It's how my slide rule works. You know what a slide rule is, right?


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
Sure. I found an old one once, wouldn't rest until I'd figured out how to use it. (Including the trig functions). Never actually used it in real life though.
Jeroen Wenting
Ranch Hand

Joined: Oct 12, 2000
Posts: 5093
sorry, meant base 10
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: sorting performance - need help with math