3 ms·

1. How is this not linear time?

by cncool 14y ago

drostie 14y ago
Because as the numbers increase, their storage requirement also increases. Suppose you have the array [1, 2, 3, ..., n]. How does storage of that array scale? You need log(n) bits to store the largest element and you need about n elements of that size (at the very least the last n/2 will have the last bit set) -- so you are operating on a data source which has size O(n log n). At least, if n is the above number. Given this, any algorithm which only uses O(n) instructions cannot asymptotically read the whole array, and this presents a fundamental limitation on the problem. Technically, there cannot be a solution better than O(n log n) for this reason -- unless you get lucky and find the duplicated element in the very first O(n) of the array, you will miss it in the last O(n log n) of the array. The larger problem is that there is a fundamental confusion here. Really you should say that the array is some permutation of [1, 2, 3, ... m] and that n = m log m is the input size, and then ask whether algorithms run in linear time relative to n, not relative to m. This allows you to read in the array. You still have the problem that you have storage which grows like 1 + log m, though.
- pantaloons 14y ago
  The larger problem is the cult of "Big O" and its use as a form of signalling in interviews. If I wanted to test whether a candidate understood Big O, I'd ask them if there was a difference between O(1) and O(0). What these companies want is to see if the candidate understands program performance in general. Big O is the vogue (in my view misguided) way to do that.
- alexchamberlain 14y ago
  I disagree. The array is stored outside of your algorithm. The algorithm is constant space.
  - JoachimSchipper 14y ago
    At least the sum needs ~log(N^2) bits. We typically assume that stuff fits in the native word size and thus takes a single cycle independent of the actual length of the number, but that's obviously not actually true (for numbers >= 2^32 or 2^64, etc.)
  - IsTom 14y ago
    You still need to read O(nlogn) bits of the array. It can't take less than O(nlogn) time.

1. How is this not linear time?

by cncool 14y ago

1. How is this not linear time?

Because as the numbers increase, their storage requirement also increases. Suppose you have the array [1, 2, 3, ..., n]. How does storage of that array scale? You need log(n) bits to store the largest element and you need about n elements of that size (at the very least the last n/2 will have the last bit set) -- so you are operating on a data source which has size O(n log n). At least, if n is the above number. Given this, any algorithm which only uses O(n) instructions cannot asymptotically read the whole array, and this presents a fundamental limitation on the problem. Technically, there cannot be a solution better than O(n log n) for this reason -- unless you get lucky and find the duplicated element in the very first O(n) of the array, you will miss it in the last O(n log n) of the array. The larger problem is that there is a fundamental confusion here. Really you should say that the array is some permutation of [1, 2, 3, ... m] and that n = m log m is the input size, and then ask whether algorithms run in linear time relative to n, not relative to m. This allows you to read in the array. You still have the problem that you have storage which grows like 1 + log m, though.

pantaloons 14y ago
The larger problem is the cult of "Big O" and its use as a form of signalling in interviews. If I wanted to test whether a candidate understood Big O, I'd ask them if there was a difference between O(1) and O(0). What these companies want is to see if the candidate understands program performance in general. Big O is the vogue (in my view misguided) way to do that.
alexchamberlain 14y ago
I disagree. The array is stored outside of your algorithm. The algorithm is constant space.
- JoachimSchipper 14y ago
  At least the sum needs ~log(N^2) bits. We typically assume that stuff fits in the native word size and thus takes a single cycle independent of the actual length of the number, but that's obviously not actually true (for numbers >= 2^32 or 2^64, etc.)
- IsTom 14y ago
  You still need to read O(nlogn) bits of the array. It can't take less than O(nlogn) time.