4 ms·
Let's say you have 2 algorithms. Constant time O(1) and exp time 2^n. It seems constant time is better. But in fact it runs always 42 years. While exp one start
by Sankozi 2y ago
Let's say you have 2 algorithms. Constant time O(1) and exp time 2^n. It seems constant time is better. But in fact it runs always 42 years. While exp one starts to run longer than millisecond for sizes bigger than number of particles in universe.
Big O says how fast complexity grows, but it doesn't say what that complexity exactly is.
Does something like that happens in real world? Yes, but of course not in such drastic ways.
- qazxcvbnm 2y agoA very exaggerated example to use exp time… Whatever your constant, for exp time, it’s going to run for times longer than the life of the universe on probably any n > 10… Since you know, log time is practically constant
- forrestthewoods 2y agoThe fact that Big O notation is sometimes misleading or not helpful is not evidence that it is not generally useful. https://www.tumblr.com/accidentallyquadratic https://www.tumblr.com/accidentallyquadratic
- qludes 2y agoAs a concept it is pretty useful for me in a handwavy astrophysics math way because I otherwise wouldn't necessarily know how to make my naive solution fit real world constraints.
- pyfon 2y agoMost of the time the constants are going to be similar. And by similar I mean < 3 orders of magnitude say. So 2^9 or adding 9 to N eats that up pretty quick.
- jhanschoo 2y agoIf you are writing everyday programs your constant factors are going to be very comparable and proportional to the size of your program, unless you have somewhere in your program hardcoded numerical constants like, run this loop 1 trillion times.
- hnfong 2y agoIf we're talking about "fantasy world" vs "real world", the "always run 42 years algorithm" surely is closer to fantasy world than most reasonable Big-O analyses... If you need to pull an example from fantasy world to illustrate your point about Big-O notation not being useful "in the real world" you're probably committing the same alleged mistakes as computational theorists...
- virgilp 1y ago> While exp one starts to run longer than millisecond for sizes bigger than number of particles in universe. You don't really know how this works, do you? I can guarantee that thera are more than 1M particles in the universe. And if you iterate 2^1M times, doing nothing, on a current computer... that's basically indistinguishable from an infinite loop.