# sorting performance - need help with math

posted 12 years ago

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 ]

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

Ranch Hand

Posts: 1332

2

posted 12 years ago

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 ]

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 ]

SCJP

Visit my download page

Dirk Schreckmann

Sheriff

Posts: 7023

Jeroen Wenting

Ranch Hand

Posts: 5093

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 12 years ago

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*

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671