5 ms·
> 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 th
by Thomashuet 4y ago
> 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.
- bjourne 4y agoNo, in Big-O notation the magnitude of positive constant factors is completely irrelevant.
- mikebenfield 4y agoThe fact that the magnitude of positive constant factors is irrelevant doesn’t mean it makes any assumptions about the cost of operations.
- dfee 4y agoGive me a sufficiently large n and I’ll give you a sufficiently large constant.
- ericpauley 4y agoFalse. The whole premise of asymptotic complexity is that the constant factor must be finite as n goes to infinity.
- tialaramex 4y agoMachines 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.
- tshaddox 4y ago> 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.
- tialaramex 4y ago> 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.
- tshaddox 4y agoSure, 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.
- tialaramex 4y agoIt'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.
- tshaddox 4y agoI 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?
- mattarm 4y agoI 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.
- varajelle 4y agoSee also the "galactic" algorithms: https://en.m.wikipedia.org/wiki/Galactic_algorithm https://en.m.wikipedia.org/wiki/Galactic_algorithm
- kevin_thibedeau 4y agoSmaller N happens a lot in the real world. Sequential search can beat binary search for sufficiently small N despite being the "worse" choice.
- sitkack 4y agoBecause in Software Engineering, layout matters. Computing Machines don't care about asymptotic behavior.
- bluefirebrand 4y agoThere 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.
- rhdunn 4y agoThe 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.
- tshaddox 4y agoIf the large number you give me depends on the n that I gave you, then what you gave me isn't a constant.
- chongli 4y agoThat'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.