Mathematical Notation & Symbols Reference

Precise mathematical notation and unambiguous pseudocode syntax prevent misinterpretations between theoretical proofs and executable software. This chapter establishes the universal mathematical symbols, asymptotic definitions, pointer conventions, and language-independent pseudocode standards used across the entire curriculum.

By the end of this chapter, you will be able to:

• Interpret and apply formal set theory, interval, and floor/ceiling notations in algorithmic contexts.
• Distinguish between asymptotic upper bounds ($O$), lower bounds ($\Omega$), and tight bounds ($\Theta$).
• Read and author standardized, language-independent algorithmic pseudocode with explicit line numbering and scope.
• Map mathematical pointer notations (HEAD, TAIL, node.next, adj[u]) to concrete memory references in C++, Java, Python, Go, and Rust.

Standard mathematical conventions used throughout the 62 chapters to describe data domains, sizes, and operational invariants:

Asymptotic notation characterizes the limiting behavior of an algorithm's runtime or memory footprint as input size $n\to \infty$.

• A[i]: Element at zero-based index $i$ in array $A$.
• length(A): Total active elements stored in structure $A$.
• capacity(A): Total allocated physical buffer slots before a resize is triggered.
• HEAD: Pointer or reference to the initial node of a linked list.
• TAIL: Pointer or reference to the terminal node of a linked list.
• node.value: Data payload contained inside a node.
• node.next: Pointer referencing the successor node.
• node.prev: Pointer referencing the predecessor node (doubly linked list).
• NULL / NIL: Ground reference denoting absence of memory address.

• $T$: A tree structure.
• root: The unique origin node possessing indegree 0.
• node.left, node.right: Left and right child references in binary trees.
• node.parent: Pointer to the direct ancestor.
• $h(u)$: Height of node $u$ (longest downward edge-path to a leaf; leaf height $=0$).
• $d(u)$: Depth of node $u$ (edges on path from root down to $u$; root depth $=0$).
• $BF(u)$: Balance Factor of node $u$, defined as $BF(u)=h(u.left)-h(u.right)$.

• $G=(V,E)$: A graph consisting of vertex set $V$ and edge set $E$.
• $|V|$ or $V$: Total count of vertices (nodes).
• $|E|$ or $E$: Total count of edges (arcs).
• $(u,v)$: Edge connecting vertex $u$ to vertex $v$.
• $w(u,v)$: Scalar weight or cost associated with edge $(u,v)$.
• $\mathrm{deg}(u)$: Degree of vertex $u$ (total incident edges).
• $\text{in-deg}(u),\text{out-deg}(u)$: In-degree and out-degree in directed graphs (digraphs).
• $adj[u]$: Adjacency list storing all vertices adjacent to $u$.

To ensure algorithms transfer seamlessly across C++, Java, Python, Go, and Rust, every algorithm in this curriculum follows a language-independent pseudocode standard.

1. Line Numbering: Explicit 1-based numbering enables step-by-step state table tracing.
2. Assignment Operator: Left arrow ← indicates assignment (reserving = for equality comparison).
3. Equality & Relations: = (equality), ≠ (inequality), <, ≤, >, ≥.
4. Logical Operators: and, or, not written in lowercase text.
5. Indentation Scoping: 4-space indentation defines block scope without language-specific braces.
6. Control Flow:
   • while <condition>:
   • for <var> ← <start> to <end>: (inclusive range)
   • for each <item> in <collection>:
   • if <condition>: ... else if <condition>: ... else:
7. Signatures:
   • Declaration: ALGORITHM Name(parameters)
   • Exit: return <value>

ALGORITHM BinarySearch(A, target)
    Input: Sorted array A of length n, target value to locate
    Output: Index of target in A, or -1 if target is not present

1.  low ← 0
2.  high ← length(A) - 1
3.  while low ≤ high:
4.      mid ← low + ⌊(high - low) / 2⌋
5.      if A[mid] = target:
6.          return mid
7.      else if A[mid] < target:
8.          low ← mid + 1
9.      else:
10.         high ← mid - 1
11. return -1

• Strict Terminology: Distinguish between worst-case runtime and Big-O upper bounds; Big-O is a mathematical envelope, while worst-case is an operational scenario.
• Logarithmic Base: In computer science, $\log n$ implies base 2 unless explicitly denoted otherwise (due to binary subdivisions).
• Pseudocode Discipline: Explicit line numbering and unambiguous assignment (←) eliminate translation errors when implementing algorithms across diverse programming languages.

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapters 1–3. MIT Press.
2. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.
3. IEEE / ACM Computing Curricula Guidelines (2020). Curriculum Guidelines for Undergraduate Degree Programs in Computer Science.