4 ms·

I would have a huge problem describing the first one as O(1). Technically the complexity is min(searched, INT_MAX), but the algorithm would also fail to produce

I would have a huge problem describing the first one as O(1). Technically the complexity is min(searched, INT_MAX), but the algorithm would also fail to produce a result if it reaches INT_MAX. Functionally, though, I would describe this algorithm as O(N). It's just a straight up linear scan of the problem space. It's unbounded, with a worst case of O(Infinity) and no upper limit on what searched can be, but it's functionally O(N) regardless. O(1) needs to basically be something like a hash key/pointer to memory address to get the result you're looking for. It will not increase linearly as the problem space increases, whereas your first example increases exactly linearly.

devmop 4y ago
It takes the same (huge) amount of time for all inputs - there's no early exit it always scans to INT_MAX. Hence O(1)
- glitchc 4y ago
  This is incorrect. Putting a finite bound on n does not reduce n to 1. n is always meant to be a finite arbitrarily large value. n=INT_MAX qualifies as arbitrarily large, especially on a 64-bit system.
  - carnitine 4y ago
    O(x) = O(1) if x is some finite constant.
  - PhineasRex 4y ago
    There is no bound on n, it always searches to INT_MAX regardless of n.
  - Sohcahtoa82 4y ago
    Big-O notation says nothing about the overall absolute size. All that matters is how the amount of work scales with the input value. If an algorithm will always take 1 billion years to complete regardless of the input, then it's still O(1).
  - 8note 4y ago
    Consider n=INT_MAX*2 or INT_MAX^2 though. The behaviour does flatline as n approaches infinity
carnitine 4y ago
That’s just not how complexity analysis works, if there’s a bound anywhere, it is O(1). The behaviour below that bound may be of more practical importance, but it’s not how O-notation works. The parent comment doesn’t make a great deal of sense for other reasons, but your objections don’t hold either.
- simiones 4y ago
  By this logic, all programs that we run are O(1), since any data structure is in practice bounded in size by your available address space (+ disk space if we want to be pedantic). So, you can replace any loop over the elements of a DS with a loop over all memory in the address space, and you will get an O(1) algorithm. In the end, it's just not a useful way of modelling the problem.
  - carnitine 4y ago
    Yes, so ordinarily we analyse an idealised algorithm running on idealised machine. However if an upper bound is clearly introduced to this idealised setting, as in the root comment, then it can’t be ignored.
    - waynesonfire 4y ago
      So an idealised machine doesn't have an arbitrary INT_MAX limit. The algorithms are O(n).
      - l33t2328 4y ago
        But playing tricks with the INT_MAX limit ignores(or, more accurately, spits in the face of) the fact that we want our computers to pretend to be idealized machines. Floats aren’t real numbers but we treat them like the mathematical object that they model for most purposes. Of course, being aware of the limits of our models are important, but abusing the tragic finitness of our models to “well actually” someone is generally not helpful.
- l33t2328 4y ago

devmop 4y ago

It takes the same (huge) amount of time for all inputs - there's no early exit it always scans to INT_MAX. Hence O(1)

glitchc 4y ago
This is incorrect. Putting a finite bound on n does not reduce n to 1. n is always meant to be a finite arbitrarily large value. n=INT_MAX qualifies as arbitrarily large, especially on a 64-bit system.
- carnitine 4y ago
  O(x) = O(1) if x is some finite constant.
- PhineasRex 4y ago
  There is no bound on n, it always searches to INT_MAX regardless of n.
- Sohcahtoa82 4y ago
  Big-O notation says nothing about the overall absolute size. All that matters is how the amount of work scales with the input value. If an algorithm will always take 1 billion years to complete regardless of the input, then it's still O(1).
- 8note 4y ago
  Consider n=INT_MAX*2 or INT_MAX^2 though. The behaviour does flatline as n approaches infinity

carnitine 4y ago

That’s just not how complexity analysis works, if there’s a bound anywhere, it is O(1). The behaviour below that bound may be of more practical importance, but it’s not how O-notation works. The parent comment doesn’t make a great deal of sense for other reasons, but your objections don’t hold either.

simiones 4y ago
By this logic, all programs that we run are O(1), since any data structure is in practice bounded in size by your available address space (+ disk space if we want to be pedantic). So, you can replace any loop over the elements of a DS with a loop over all memory in the address space, and you will get an O(1) algorithm. In the end, it's just not a useful way of modelling the problem.
- carnitine 4y ago
  Yes, so ordinarily we analyse an idealised algorithm running on idealised machine. However if an upper bound is clearly introduced to this idealised setting, as in the root comment, then it can’t be ignored.
  - waynesonfire 4y ago
    So an idealised machine doesn't have an arbitrary INT_MAX limit. The algorithms are O(n).
    - l33t2328 4y ago
      But playing tricks with the INT_MAX limit ignores(or, more accurately, spits in the face of) the fact that we want our computers to pretend to be idealized machines. Floats aren’t real numbers but we treat them like the mathematical object that they model for most purposes. Of course, being aware of the limits of our models are important, but abusing the tragic finitness of our models to “well actually” someone is generally not helpful.
l33t2328 4y ago