Win a copy of Testing JavaScript Applications this week in the HTML Pages with CSS and JavaScript forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Liutauras Vilda
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • fred rosenberger
  • salvin francis
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Carey Brown

sorting performance - need help with math

 
Ranch Hand
Posts: 4716
9
Scala Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
blacksmith
Posts: 1332
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Posts: 4716
9
Scala Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
Sheriff
Posts: 7023
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Side note, lg is a common representation for log base 2.
 
Ranch Hand
Posts: 5093
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
lowercase baba
Posts: 12871
62
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 5093
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
sorry, meant base 10
 
Consider Paul's rocket mass heater.
    Bookmark Topic Watch Topic
  • New Topic