Computer science combines mathematical notation and structured symbolic conventions to describe how information is represented, processed, stored, and transmitted. Algorithm notation communicates a finite sequence of well-defined operations that transforms input into output. Pseudocode expresses algorithmic logic without requiring the exact syntax of a particular programming language. Flowcharts use standardized shapes and arrows to represent processing steps, decisions, inputs, outputs, and control flow. Mathematical notation is used to define sets, relations, functions, sequences, graphs, trees, and recurrence relations. Computational complexity notation describes how an algorithm's resource requirements grow with input size. Big-O notation provides an asymptotic upper bound, Big-Omega provides an asymptotic lower bound, and Big-Theta describes a tight asymptotic bound. These notations characterize growth rates rather than exact execution times. Data structures use symbols and diagrams to represent arrays, linked lists, stacks, queues, trees, heaps, hash tables, and graphs. Graph notation defines vertices and edges, while tree notation describes hierarchical relationships. Recurrence relations are used to analyze recursive algorithms. Formal languages use alphabets, strings, grammars, and production rules. Automata theory describes computational models such as finite-state machines and pushdown automata. Different textbooks and subfields may use different conventions, so definitions of variables, indexing, input size, and asymptotic assumptions must be stated clearly.
Computer Science: Algorithms and Computational Notation
Computer science notation describes algorithms, data structures, computational processes, formal languages, complexity, and mathematical models of computation. It uses pseudocode, mathematical expressions, set notation, logical operators, recurrence relations, graphs, trees, and asymptotic symbols to specify and analyze computational problems.
Algorithmic running-time notation: T(n) ∈ O(f(n)) when T(n) is asymptotically bounded above by a constant multiple of f(n). Common growth classes include O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), and O(n!). A recurrence example is T(n) = 2T(n/2) + Θ(n), which has solution T(n) = Θ(n log n) under the usual divide-and-conquer assumptions.
Explanation
Variables
| Symbol | Meaning | Unit |
|---|---|---|
n | Input size or number of elements. | Count |
T(n) | Time or resource function as a function of input size. | Depends on the resource being measured. |
S(n) | Space complexity as a function of input size. | Bytes, words, or abstract storage units. |
O(f(n)) | Asymptotic upper-bound class. | Not a physical unit. |
Ω(f(n)) | Asymptotic lower-bound class. | Not a physical unit. |
Θ(f(n)) | Asymptotically tight-bound class. | Not a physical unit. |
V | Vertex set of a graph. | Set of vertices. |
E | Edge set of a graph. | Set of edges. |
G | A graph, often defined as G = (V, E). | Mathematical object. |
Σ | Alphabet of a formal language. | Set of symbols. |
ε | Empty string in formal-language notation. | Not applicable. |
Example or application
A worked example has not yet been added.
Definition
Computer science notation is the collection of mathematical, logical, graphical, and symbolic conventions used to represent algorithms, computational structures, formal models, and the resource requirements of computational processes.
Purpose
To specify computational procedures, describe data structures, reason about correctness, analyze resource usage, and construct mathematical models of computation.
Importance
Consistent computational notation allows algorithms to be communicated independently of programming languages, supports formal verification, enables complexity comparisons, and provides a foundation for data structures, automata theory, compiler design, and theoretical computer science.
Algorithm And Pseudocode Symbols
| Symbol | Meaning | Example |
|---|---|---|
← | Assignment in many pseudocode conventions. | x ← 5. |
← or := | Assignment notation; the exact choice depends on the pseudocode or formal language. | sum := sum + x. |
== | Equality comparison in many programming languages. | if x == y. |
≠ | Mathematical inequality. | x ≠ y. |
∧ | Logical AND. | P ∧ Q. |
∨ | Logical OR. | P ∨ Q. |
¬ | Logical NOT. | ¬P. |
∀ | For all. | ∀x ∈ S. |
∃ | There exists. | ∃x ∈ S. |
∈ | Is an element of a set. | x ∈ S. |
∉ | Is not an element of a set. | x ∉ S. |
∅ | Empty set. | S = ∅. |
Complexity Notation
| Notation | Meaning | Example |
|---|---|---|
O(1) | Constant asymptotic growth. | Accessing an array element by a valid index in a conventional array model. |
O(log n) | Logarithmic asymptotic growth. | Binary search in a sorted array. |
O(n) | Linear asymptotic growth. | A single traversal of an array. |
O(n log n) | Linearithmic asymptotic growth. | Typical comparison-based sorting algorithms such as mergesort. |
O(n²) | Quadratic asymptotic growth. | A straightforward nested-loop comparison over n elements. |
O(2ⁿ) | Exponential asymptotic growth. | Some exhaustive algorithms that explore all subsets. |
O(n!) | Factorial asymptotic growth. | Exhaustive enumeration of all permutations. |
Data Structure And Graph Notation
| Notation | Meaning |
|---|---|
A[i] | Element at index i in array A. |
L → next | A conceptual pointer or reference to the next node in a linked structure. |
Stack | A last-in, first-out structure; push and pop are common operations. |
Queue | A first-in, first-out structure; enqueue and dequeue are common operations. |
G = (V, E) | A graph defined by a vertex set V and an edge set E. |
|V| | Number of vertices in a graph. |
|E| | Number of edges in a graph. |
deg(v) | Degree of vertex v in an undirected graph. |
d(u, v) | Distance or weight-related quantity between vertices u and v, as defined by the graph model. |
T(n) | Recurrence or complexity function for an algorithm of input size n. |
Formal Language Notation
| Symbol | Meaning |
|---|---|
Σ | Finite alphabet of a formal language. |
Σ* | Set of all finite strings over alphabet Σ, including the empty string. |
Σ⁺ | Set of all nonempty finite strings over alphabet Σ. |
ε | Empty string. |
L | A formal language, commonly a subset of Σ*. |
→ | Production or rewriting relation in a grammar. |
∪ | Union of sets or languages. |
* | Kleene star when applied to a language or regular expression. |
δ | Transition function in many automata definitions. |
q₀ | Initial state in a finite-state machine. |
F | Set of accepting or final states in common automata notation. |
Worked Examples
| Example | Given | Analysis | Result | Notation |
|---|---|---|---|---|
Linear-time algorithm | An algorithm examines every element of an array of n elements exactly once. | The number of examinations grows proportionally to n. | Time complexity is Θ(n). | |
Binary search | A sorted array contains 1024 elements. | Binary search approximately halves the remaining search interval at each step. Since 2¹⁰ = 1024, the number of halving steps is about 10. | The algorithm has O(log n) time complexity. | |
Graph size | An undirected graph contains 8 vertices and 12 edges. | The graph contains 8 vertices and 12 edges. | |V| = 8 and |E| = 12. | |
Set membership | S = {2, 4, 6, 8}. | 4 belongs to the set, while 5 does not. | 4 ∈ S and 5 ∉ S. |
Common Misinterpretations
| Misinterpretation | Correction |
|---|---|
Treating O(f(n)) as an exact running-time formula. | Big-O describes an asymptotic upper bound and suppresses constant factors and lower-order terms. |
Assuming O(n) always means an algorithm is faster than O(log n) for every small input. | Asymptotic notation describes growth for sufficiently large input sizes; constants and implementation details also matter. |
Confusing assignment with equality comparison. | Use the notation defined by the pseudocode or programming language; ←, =, :=, and == are not universally interchangeable. |
Assuming every graph is directed. | Specify whether edges are directed or undirected and whether they carry weights. |
Treating ε as the number zero. | In formal-language theory, ε represents the empty string, which is different from the numeric value 0. |
Reference
Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms
Sipser, Introduction to the Theory of Computation
Knuth, The Art of Computer Programming
Rosen, Discrete Mathematics and Its Applications
Related Topic
SCI-REF-006-091
SCI-REF-006-095
SCI-REF-006-098
SCI-REF-006-099
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.
Suggest a correction or source · More in Scientific Symbols & Notation