4 ms·

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

tialaramex 4y ago
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.
- 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 ago
      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.
      - tialaramex 4y ago
        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.
        tshaddox 4y ago
        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?
- drran 4y ago
  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.
- benibela 4y ago
  If N is a 32-bit machine integer, then O(N^2) is actually O(1)

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.

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 ago
    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.
    - tialaramex 4y ago
      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.
      - tshaddox 4y ago
        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?
drran 4y ago
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.
benibela 4y ago
If N is a 32-bit machine integer, then O(N^2) is actually O(1)