Remix clone Hacker News

> Big O notation also suffers from this - it's almost useless for real world problems.

This is quite a bold claim. Yeah "in the real world" you often need to take into consideration the constant factors... but to go this far to say that Big O is useless? It's very useful to figure out what would likely work (or not) for your problem, given that you know the data size - I used it for exactly that, many many times.

▲

Sankozi 6 days ago | parent [-]

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.

▲

forrestthewoods 6 days ago | parent | next [-]

The 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

	▲	qludes 6 days ago \| parent [-]
		As 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.

▲

jhanschoo 6 days ago | parent | prev | next [-]

If 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 5 days ago | parent | prev | next [-]

If 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 5 days ago | parent | prev | next [-]

> 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.

▲

qazxcvbnm 6 days ago | parent | prev | next [-]

A 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

▲

pyfon 6 days ago | parent | prev [-]

Most 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.