Hacker News Reader

Comment by Thomashuet | Hacker News Reader

> Big-O assumes all "operations" are equally costly. That's not the case on real hardware, and pretty much never has been. Some instructions take more cycles than others.

No, it only assumes that there is a constant factor between the fastest and slowest "operations". It does not matter that one instruction can take a thousand times more cycles than another, if you have n² fast instructions and n slow ones, the running time will still be dominated by the n² fast ones for large n.

> Big-O assumes that only asymptotic behavior matters.

Yes, and this is the only simplification that it does.

View on HN

No, in Big-O notation the magnitude of positive constant factors is completely irrelevant.

The fact that the magnitude of positive constant factors is irrelevant doesn’t mean it makes any assumptions about the cost of operations.

Give me a sufficiently large n and I’ll give you a sufficiently large constant.

False. The whole premise of asymptotic complexity is that the constant factor must be finite as n goes to infinity.

Machines don't do infinity. This article isn't about an imaginary computer with an infinitely long paper tape from a thought experiment, it's about a real computer, just like the ones many HN readers work with every day.

As a result k*N can actually be bigger than N^2 when in fact N isn't "an integer" in a mathematical sense but merely a 32-bit machine integer, for example - simply by k being more than 4 billion in that case.

> This article isn't about an imaginary computer with an infinitely long paper tape from a thought experiment, it's about a real computer, just like the ones many HN readers work with every day.

If you're determined to throw out any concepts which technically only apply to theoretical computers with unbounded memory, then go all the way. Your actual physical computer can trivially iterate through all of its possible states in a fixed amount of time. The halting problem is trivially solvable for all programs that your actual physical computer can execute. Your actual physical computer isn't even Turing complete.

> Your actual physical computer can trivially iterate through all of its possible states in a fixed amount of time.

Nope. You're in an imaginary world again. This universe will cease to support computation a long time before it would be possible for the computer to try all possible states.

Sure, but that's like saying that your computer could experience power outages or hardware failures at any time. That's true, but we don't normally consider those as limitations to the computational capabilities of your computer.

It's a difference in kind. The computer could experience a power outage, it could experience a hardware failure, but regardless it and all other real computers will cease to operate long before it would be able to explore all possible states.

I don’t think it’s a difference in kind. Given some specific physical computer, how would you determine an n such that n states are iterable on that computer but n+1 states are not iterable due to the universe’s ability to support computation?

Algorithms and programs are different things. An implementation of the algorithm is called a program. Big-O is used for comparing of algorithms. An algorithm can be implemented in different ways. Performance of the program can be measured precisely. Different implementations of the same algorithm will have different performance. When precise information is available, assumptions are useless. When precise information is not available, at design stage, assumptions are used to compare different algorithms.

If N is a 32-bit machine integer, then O(N^2) is actually O(1)

I think that makes sense only for smaller n. At some point your "sufficiently large constant" will need to essentially be computed from the "worse big-O" algorithm to slow the "better big-O" algorithm down enough. E.g. making an O(N) as slow as an O(N^2) algorithm would require a sufficiently large constant roughly equivalent to N^2, at which point you really just have turned the O(N) into O(N^2) in practice.

See also the "galactic" algorithms: https://en.m.wikipedia.org/wiki/Galactic_algorithm

Smaller N happens a lot in the real world. Sequential search can beat binary search for sufficiently small N despite being the "worse" choice.

Because in Software Engineering, layout matters. Computing Machines don't care about asymptotic behavior.

There is something of a bounded limit on how long a single operation could possibly take, assuming your hardware isn't just plain faulty.

Yes, for the purposes of Big O, we define operations such that they aren't simply 1:1 instructions to the hardware, but they should be basic commands offered by your programming language.

If the basic commands in your language are taking extremely high bounded amounts of time, that's a sign your programming language is extremely poorly optimized, not that Big O isn't useful.

A read that hits the network could take a pretty long time.

That's why, when dealing with network algorithms, you analyze the IO complexity in addition to time complexity.

The idea behind Big-O notation is how the time generally varies as you increase the number of items for a given algorithm on a given data structure/data set. That is if you plot a graph `y=f(x)` where `f(x)` is the time taken to perform that operation and x is the number of items you are performing it on. You can then match that resulting curve to a polynomial or other mathematical expression, and Big-O is the dominant term in that expression without any associated scale factors (e.g. for 6x^3 + 2x^2 + 7 you have an O(n^3) algorithm).

Sure, you can choose a large constant such that numerically it is equal to or smaller than O(n^2) for a given n, but as you vary n then O(1) should approximate a flat `y=N` line, while O(n^2) should approximate a parabola and would result in values larger and smaller than N as you vary it.

If the large number you give me depends on the n that I gave you, then what you gave me isn't a constant.

That's not how constants work in mathematics. You have to give the constant first and cannot change it later. That is what it means for a quantity to be constant.

Reply on news.ycombinator.com