>
> I do not think that the character of the problem was to induce some
> solution by enforcing an artificial size constraint on it like it has
> to be coded on a 32 bit machine.
True. But I do work with situations where such solutions are the
'bread and butter' of soliciting more work. Academic
It doesn't really leave us anywhere, I think. By the way -- I cannot
prove, as of yet, that there is no solution as specified (O(n) time,
O(1)) asymptotically, I am just saying that: 1. yours is not
appropriate, and 2. that the known algorithmic bounds on similar
problems do not make me optimisti
On Aug 25, 2:00 pm, wbspresslyjr <[EMAIL PROTECTED]> wrote:
> You are mixing up implementation with theory here. The study of
I would argue that neither of us are mixing up anything. I agree, that
in the infinite sense, an O(n) solution is absurd. However, the reason
I pointed to the trail of m
You are mixing up implementation with theory here. The study of
Algorithms is a rigorous and abstract field. Note the use of the word
abstract... This means that we are not talking about computers (32bit,
64bit)... we are talking about the nature of mathematics and problem
solving...
Mathematical
"Always (notice my stipulation of 32 bit). However, regardless of the
size of an integer (in bits) there is _always_ a fixed number of bits
that can represent it in the manner I explained. "
Ther is no 32 bit requirement. When you are talking asymptotically, as
n grows infinitely large, there is
I am not sure that this is exactly the element uniqueness problem,
however -- does it matter in this problem statement that you are told
that there is a repetition, and that the goal is to find it? I am not
sure if that changes the problem or not...
I agree with you though, that there is no solut
Dyanesh, ... precisely!
On 8/25/07, Dhyanesh (ધયાનેશ) <[EMAIL PROTECTED]> wrote:
>
> If you think of your DP solution, it is almost the same as the previous
> O(n) solution you gave. That one is also DP in way that you store just one
> previous solution.
> -Dhyanesh
>
> On 8/24/07, Lego Haryanto <
I am afraid this problem CANNOT be solved faster than O(n*log(n)) . If you
can find a single repeated element in an array in O(n) then you can solve
the element uniqueness problem. However this problem cannot be done in
better than O(n * log(n) ).
http://en.wikipedia.org/wiki/Element_uniqueness_pro
If you think of your DP solution, it is almost the same as the previous O(n)
solution you gave. That one is also DP in way that you store just one
previous solution.
-Dhyanesh
On 8/24/07, Lego Haryanto <[EMAIL PROTECTED]> wrote:
>
> I should take my statement regarding the O(n) space for DP back .
