Data Structures with Generic Types in C++/

...

/

The Model of Computation

The Model of Computation

Understand the theoretical running times of operations on data structures.

We'll cover the following...

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

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 w-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) ...

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy