In a seminal paper of 1989, Fredman and Saks proved lower bounds for some important data‐structure problems in the cell probe model. This model assumes that data structures are stored in memory with a known word length. In this paper we consider random access machines (RAMs) that can add, subtract, compare, multiply and divide integer or real numbers, with no size limitation. These are referred to as algebraic RAMs . We prove new lower bounds for two important data‐structure problems, union‐findand dynamic prefix sums . To this end we apply the generalized Fredman–Saks techniqueintroduced by the authors in a previous paper. The generalized technique relies on a certain well‐defined function, Output Variability , that characterizes in some sense the power of the computational model. Fredman and Saks' work implied bounds on output variability for the cell probe model; in this paper we provide the first bounds for algebraic RAMs, and show that they suffice for proving tight lower bounds for useful problems.An important feature of the problems we consider is that in a data structure of size n , the data stored are members of {0,\ldots,n} . This makes the derivation of lower bounds for such problems on a RAM without word‐size limitations a particular challenge; previous RAM lower bounds we are aware of depend on the fact that the data for the computation can vary over a large domain.
