3 ms·

I very much doubt that the OP can solve either problem 1 or problem 2 with constant space. Hint: even storing an additional integer N requires \Omega(log(N)) sp

by ckuehne 14y ago

I very much doubt that the OP can solve either problem 1 or problem 2 with constant space. Hint: even storing an additional integer N requires \Omega(log(N)) space. Edit: For the down voter: I searched around and found a discussion of the puzzle [1]. Please go ahead and read it. [1] http://books.google.de/books?id=415loiMd_c0C&lpg=PP1&dq=muthukrishnan+data+stream+algorithms&hl=el&pg=PA1&redir_esc=y#v=onepage&q=muthukrishnan%20data%20stream%20algorithms&f=false http://books.google.de/books?id=415loiMd_c0C&lpg=PP1&#38...

hristov 14y ago
I am not sure how you got downvoted but the constant space requirement seems a little puzzling. When the problem says that you are given a list of n numbers (or, more correctly, n-1) you are already in linear space. You have to store the list somehow. Maybe they meant "constant additional space". Or constant space for the data you are using in addition to the space required for the inputs. That however tends to go against the main principles of complexity theory and O-notation. The main principle of O notation is that you mostly care on how things grow as n becomes large. Thus, constant terms should be deleted if you have a linear term. In other words, if you have something that adds constant space to linear space, you get linear space. Thus, if you already have something that requires linear space, and have to add something else to it, it is not that important (for complexity theory purposes) if the second thing is in constant space, or log space or even linear space, as long as it is smaller or equal to linear space.
- gnud 14y ago
  It's fairly standard to talk about how much auxiliary space an algorithm needs - in sorting, for example. I guess that's what the author means.
ckuehne 14y ago
Thinking about it, it comes down to the level of analysis you choose. If you assume constant space per integer, then it is indeed solvable with O(1) additional space. For example, this is usually assumed when analyzing sorting algorithms and I guess this is also what the author had in mind.
- pantaloons 14y ago
  If you limit n then than the algorithm is actually O(1) time too -- his answer is wrong either way.

by ckuehne 14y ago

hristov 14y ago

I am not sure how you got downvoted but the constant space requirement seems a little puzzling. When the problem says that you are given a list of n numbers (or, more correctly, n-1) you are already in linear space. You have to store the list somehow. Maybe they meant "constant additional space". Or constant space for the data you are using in addition to the space required for the inputs. That however tends to go against the main principles of complexity theory and O-notation. The main principle of O notation is that you mostly care on how things grow as n becomes large. Thus, constant terms should be deleted if you have a linear term. In other words, if you have something that adds constant space to linear space, you get linear space. Thus, if you already have something that requires linear space, and have to add something else to it, it is not that important (for complexity theory purposes) if the second thing is in constant space, or log space or even linear space, as long as it is smaller or equal to linear space.

gnud 14y ago
It's fairly standard to talk about how much auxiliary space an algorithm needs - in sorting, for example. I guess that's what the author means.

ckuehne 14y ago

Thinking about it, it comes down to the level of analysis you choose. If you assume constant space per integer, then it is indeed solvable with O(1) additional space. For example, this is usually assumed when analyzing sorting algorithms and I guess this is also what the author had in mind.

pantaloons 14y ago
If you limit n then than the algorithm is actually O(1) time too -- his answer is wrong either way.