Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in Java

The Model of Computation

Explore the word-RAM computational model used to analyze data structure efficiency. Understand memory allocation, operation costs, and the differences between worst-case, amortized, and expected running times. This lesson equips you with knowledge to assess data structure performance realistically.

We'll cover the following...

We can analyze the theoretical running times of operations on the data structures we study. To do this precisely, we need a mathematical model of computation. For this, we use the w–bit word–RAM model.

Computer memory

RAM stands for Random Access Machine. In this model, we have access to a random access memory consisting of cells, each of which stores a ww–bit word. This implies that a memory cell can represent, for example, any integer in the set {0,...,2w−1}\{0,...,2^w −1\}.

In the word–RAM model, basic operations on words take constant time. This includes arithmetic operations (+,−,∗,/,%)(+, −, ∗, /, \%), comparisons (<,>,=,≤,≥)(<, >, =, \le, \ge), and bitwise boolean operations (bitwise–AND, OR, and exclusive–OR).

Any cell can be read or written in constant time. A computer’s memory is managed by a memory management system from which we can allocate or deallocate a block of memory of any size we would like. Allocating a block of memory of size kk ...