Hacker News Reader

Comment by dfee | Hacker News Reader

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

If the large number you give me depends on the n that I gave you, then what you gave me isn't a 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.

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.

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.

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.

Reply on news.ycombinator.com