Primitive Operations & Cost Model

Every algorithm ever written—from the simplest loop to the most sophisticated machine learning model—ultimately reduces to a sequence of operations on primitive data types. Addition, comparison, assignment, bit manipulation: these atomic operations form the vocabulary from which all computational behavior is constructed.

Understanding what operations are permitted on primitive types, and how they behave, is not merely a matter of language syntax. It is the foundation upon which we reason about algorithms, analyze complexity, and make engineering decisions that scale across billions of operations.

Before enumerating specific operations, we must establish what qualifies as a primitive operation in the context of data structures and algorithms.

Definition:

A primitive operation is an atomic computational step that:

1. Operates directly on primitive data types (integers, floating-point numbers, characters, booleans)
2. Executes in bounded, constant time regardless of the magnitude of operands
3. Maps closely to hardware instructions available on the underlying processor
4. Cannot be decomposed into simpler computational steps at the algorithmic level

This definition has profound implications. When we analyze algorithm complexity, we count primitive operations. When we claim an operation is O(1), we're asserting it can be treated as a primitive operation for analytical purposes.

Why This Matters:

Consider the difference between adding two integers and concatenating two strings:

• a + b (integers): Two fixed-size operands combine in a single CPU instruction
• s1 + s2 (strings): Every character must be copied; time grows with string lengths

The first is primitive; the second is not. Confusing the two leads to catastrophic performance misjudgments. Engineers who treat string concatenation in a loop as 'simple addition' discover O(n²) behavior where they expected O(n).

This distinction—primitive versus composite operations—is the first mental tool you need for algorithmic reasoning.

Primitive operations can be systematically classified into five fundamental categories, each serving distinct computational purposes. Understanding these categories provides a complete vocabulary for describing algorithmic behavior.

Each category represents a different axis of computation:

• Arithmetic operations transform numerical values
• Relational operations establish ordering and equality
• Logical operations combine truth values
• Bitwise operations manipulate binary representations
• Assignment operations move data between memory locations

Together, these five categories are computationally complete for primitive types—any transformation you need to perform on primitive data can be expressed as a composition of these operations.

Arithmetic operations perform mathematical computations on numeric primitive types (integers and floating-point numbers). They form the computational core of most algorithms.

Hardware Mapping:

Each arithmetic operation maps to dedicated CPU instructions:

Modern CPUs execute these instructions in 1-4 clock cycles, making them truly constant-time at the hardware level. This direct mapping is why we treat arithmetic as primitive operations in algorithm analysis.

Relational operations compare two values and produce a boolean result. They are the foundation of branching (if-else decisions) and ordering (sorting, searching).

The Role of Comparisons in Algorithms:

Relational operations are the decision points in algorithms. Consider binary search:

if (arr[mid] < target)
    search right half
else if (arr[mid] > target)
    search left half
else
    found!

Every comparison eliminates half the search space. The logarithmic efficiency of binary search directly depends on relational operations being O(1). If comparisons were expensive, the entire analysis would change.

Comparison-Based Lower Bounds:

A profound theoretical result: any comparison-based sorting algorithm requires at least O(n log n) comparisons in the worst case. This lower bound assumes each comparison is primitive. The insight extends throughout algorithm theory—the number of primitive comparisons often determines algorithmic limits.

Logical operations implement Boolean algebra, operating on truth values to produce new truth values. They are the combinators that allow complex conditions to be built from simple comparisons.

Short-Circuit Evaluation:

A critical semantic detail: most languages implement short-circuit evaluation for AND and OR:

• A && B: If A is false, B is never evaluated (result is already false)
• A || B: If A is true, B is never evaluated (result is already true)

This is not merely an optimization—it changes program semantics. Code like ptr != null && ptr->value == target relies on short-circuiting to avoid null dereference. Understanding short-circuit behavior is essential for both correctness and performance.

De Morgan's Laws:

Two fundamental equivalences govern logical transformation:

• NOT (A AND B) ≡ (NOT A) OR (NOT B)
• NOT (A OR B) ≡ (NOT A) AND (NOT B)

These laws are invaluable for simplifying complex conditions and are used extensively in query optimization, compiler transformations, and algorithm design.

Bitwise operations manipulate integers at the level of individual bits—the raw binary representation. They provide direct control over data representation and enable powerful low-level optimizations.

Practical Applications:

Bitwise operations appear throughout systems programming and algorithm optimization:

These patterns appear constantly in competitive programming, embedded systems, and performance-critical code. The XOR swap, for instance, exchanges two values using only bitwise operations—no temporary variable needed.

Assignment operations transfer values between memory locations. Unlike other operations that produce values, assignment produces a side effect: modifying the state of memory.

The Semantics of Assignment:

For primitive types, assignment means copying the value:

int a = 5;
int b = a;  // b gets a COPY of 5
b = 10;     // a is still 5

This is value semantics—each variable holds its own independent copy. This contrasts sharply with reference semantics for non-primitive types, where assignment copies a reference (pointer) rather than the data itself.

Memory Model Implications:

At the hardware level, assignment involves:

1. Evaluating the right-hand side expression
2. Storing the result in the memory location of the left-hand side

For primitives fitting in CPU registers (most integers, all floats), this is a single MOV instruction. The operation is O(1) because the data size is fixed and bounded—we copy the same number of bytes regardless of the value.

Beyond knowing what operations exist, understanding their semantic guarantees is essential for writing correct algorithms.

Undefined Behavior:

Certain operations have undefined behavior in many languages:

• Integer overflow in C/C++ (signed)
• Division by zero
• Shift by negative amount or by more than the bit width

Undefined behavior means the language specification makes no guarantees—the compiler can do anything, including producing seemingly impossible results. Understanding these boundaries is essential for writing robust code.

We've established a complete taxonomy of primitive operations—the atomic building blocks of all computation.

What's Next:

Now that we understand what operations exist, the critical question becomes: why are these operations considered O(1)? The next page explores the constant-time nature of primitive operations in depth, examining the hardware and theoretical foundations that justify treating these operations as atomic steps in algorithm analysis.