Algorithms and Computation (very basic)

GRE Math Subject · Axiom Academy

LESSON Algorithms and Computation (very basic) Explore Big-O notation, algorithm efficiency, Turing machines, and decidability Big-O notation measures algorithm efficiency by describing how runtime scales with input size n . Common complexities (from best to worst): O(1) — Constant time (lookup in hash table) O( n) — Logarithmic (binary search) O(n n) — Linearithmic (merge sort) O(n^2) — Quadratic (bubble sort) O(2^n) — Exponential (brute force) Example: A function that takes 5n² + 3n + 7 operations is O(n^2) because the dominant term is n². Time Complexity vs Space Complexity : Time: How many operations (proportional to input size) Space: How much memory the algorithm uses Example: Linear Search vs Binary Search A Turing machine is a theoretical model of computation consisting of: An infinite tape divided into cells A read/write head that moves along the tape A finite set of states and transition rules Key insight: Turing machines can compute any function that is "computable" (Church-Turing thesis). They formalize what we mean by an algorithm. Deterministic vs Non-deterministic: DTM: One transition per state-symbol pair NTM: Multiple possible transitions (explores branches in parallel) Decidability refers to whether a problem can be solved by an algorithm that always terminates with YES or NO. Decidable problems: Algorithm exists that solves it completely Is a string in a given language? Does a graph have a Hamiltonian path?

This is the written version of the interactive lesson above. See the full GRE Math Subject course.