Study guide
5.1 Algorithm Efficiency: Linear, Quadratic, Exponential, and Logarithmic Growth
Praxis Computer Science 5652
Track your progress as you read
Finished sections get a check mark.
1 Chapter 1: Praxis 5652 Exam Overview and ETS Pseudocode
1.1 Praxis 5652 Test Facts, Scoring, and Registration 1.2 Official ETS Pseudocode Notation and Tracing Strategy
2 Chapter 2: Impacts of Computing: Innovation, Access, and Effects
2.1 Computing for Creativity, Problem Solving, Communication, and Innovation 2.2 Equal Access, the Digital Divide, and Accessibility 2.3 Beneficial and Harmful Effects of Computing Innovations
3 Chapter 3: Impacts of Computing: Intellectual Property, Ethics, Privacy, and Security
3.1 Intellectual Property: Copyright, Open Source, and Creative Commons 3.2 Ethical and Unethical Computing Practices and Their Implications 3.3 Privacy, Security, Data Collection, and Local vs. Cloud Storage
4 Chapter 4: Algorithms and Computational Thinking: Abstraction, Decomposition, Number Bases, and Representation
4.1 Abstraction and Abstraction Hierarchies 4.2 Decomposition, Pattern Recognition, and Developing Algorithms 4.3 Number Bases: Binary, Octal, Decimal, and Hexadecimal 4.4 Algorithm Formats: Natural Language, Flowcharts, Pseudocode, and Tracing
5 Chapter 5: Algorithms: Efficiency, Limits of Computing, and Randomization
5.1 Algorithm Efficiency: Linear, Quadratic, Exponential, and Logarithmic Growth 5.2 Limits of Computing: Unsolvable Problems, Intractability, and Heuristics 5.3 Randomization, Random vs. Pseudorandom Numbers, and Scaling to a Range
6 Chapter 6: Algorithms: Searching, Sorting, and Recursion
6.1 Searching Algorithms: Linear Search and Binary Search 6.2 Sorting Algorithms: Tracing, Comparisons, Correctness, and Efficiency 6.3 Recursion: Base Cases, Tracing, Errors, and Iterative Equivalents
7 Chapter 7: Programming: Variables, Data Types, Strings, and Expressions
7.1 Variables, Data Types, and Type Conversion 7.2 Strings and String Operations 7.3 Operators, Precedence, Expressions, and Formulas 7.4 Boolean Expressions, Truth Tables, and Boolean Algebra
8 Chapter 8: Programming: Selection, Iteration, and Writing Code
8.1 Sequence and Selection: if, else, Chained and Nested Conditions 8.2 Iteration: for, while, do … while, and repeat … until Loops 8.3 Reading, Completing, and Modifying Code
9 Chapter 9: Programming: Procedures, Arrays, and Data Structures
9.1 Procedures, Parameters, Return Values, Nested Calls, and Scope 9.2 Arrays, Lists, and Two-Dimensional Arrays 9.3 Stacks, Queues, and Dictionaries (Maps)
10 Chapter 10: Programming: Correctness, Errors, Testing, and Code Quality
10.1 Program Correctness: Preconditions, Postconditions, Invariants, and Testing vs. Proof 10.2 Error Types and Debugging Techniques 10.3 Choosing Useful Test Cases: Boundaries, Partitions, Coverage, and Regression 10.4 Extensibility, Modifiability, and Reusability: Constants and Parameterization 10.5 Documentation, Code Reviews, Peer Feedback, and End-User Feedback
11 Chapter 11: Programming: Events, Usability, Input Validation, and APIs
11.1 Event-Driven Programming, Asynchronous Events, and Concurrency 11.2 Usability, Meaningful Error Messages, and Input Validation vs. Verification 11.3 Libraries and APIs: Reading Definitions, Making Calls, and Weighing Trade-offs
12 Chapter 12: Programming: Languages, Tools, Paradigms, and Object-Oriented Design
12.1 Low- and High-Level Languages, Compilers and Interpreters, and IDEs 12.2 Programming Paradigms: Procedural, Object-Oriented, and Others 12.3 Classes, Objects, Instance Variables, Methods, and Encapsulation 12.4 Inheritance, Polymorphism, and Overloading vs. Overriding
13 Chapter 13: Data: Bits, Encoding, Compression, and Encryption
13.1 Bits and Bytes: Why Binary, Storage Calculations, and Signed Integers 13.2 Encoding Text, Images, and Sound 13.3 Lossless and Lossy Compression: Run-Length Encoding, Huffman Coding, and Media Formats 13.4 Encoding vs. Encryption, Symmetric and Public-Key Encryption, and Their Trade-offs
14 Chapter 14: Data: Analysis Tools, Simulation, Storage, and Collection
14.1 Analyzing Data with Spreadsheets: Cleaning, Transforming, and Visualizing 14.2 Simulation and Modeling 14.3 Files, Databases, and Storage Requirements: Scale, Redundancy, and Backup 14.4 Collecting, Aggregating, and Generating Data: Public Data Sets, Surveys, Sensors, and Crowdsourcing
15 Chapter 15: Computing Systems: Hardware, Operating Systems, and Computing Environments
15.1 Hardware Components and the Fetch–Decode–Execute Cycle 15.2 Operating Systems, Software Components, and Resource Issues 15.3 Embedded Systems, the Internet of Things, and Types of Computing Systems 15.4 Local, Network, and Cloud Computing and Storage; How Binary Data Are Stored
16 Chapter 16: Networks, the Internet, the Web, and Cybersecurity
16.1 Network Types and Wired and Wireless Communication 16.2 Network Hardware and Layered Network Models (OSI and TCP/IP) 16.3 Network Performance: Bandwidth, Latency, Load, and Estimating Needs 16.4 How the Internet Works: Protocols, IP Addressing, DNS, URLs, and Reliability 16.5 The Web: HTTP, HTML and Markup Languages, Browsers, Servers, and Clients 16.6 Cybersecurity: The Five Pillars, Strong Passwords, Security Strategies, and Trade-offs
5.1 Algorithm Efficiency: Linear, Quadratic, Exponential, and Logarithmic Growth
Key Takeaways Explain This Topic AI
Big-O notation describes how an algorithm's work grows with input size n, ignoring constant factors and lower-order terms.
From slowest-growing to fastest-growing: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).
When n doubles, a logarithmic algorithm needs about one more step, a linear algorithm does twice the work, and a quadratic algorithm does four times the work.
Sequential blocks add, so the largest term dominates; nested loops multiply; a loop variable that doubles or halves each pass gives logarithmic growth.
Brute-force algorithms that try every ordering of n items, such as checking every route for a traveling salesperson, take factorial time.
Last updated: September 2026
What this competency asks
Under limits of computing, ETS asks you to identify and compare algorithms that are linear, quadratic, exponential, or logarithmic . One ETS sample question describes an algorithm that generates every possible ordering of a salesperson's cities and evaluates each one. The running time is factorial in the number of cities. Your job is to look at an algorithm and name its growth class.
Why we count steps instead of seconds
Measured running time depends on the processor, the language, and other programs running at the same time. To compare algorithms , computer scientists count how many basic operations (comparisons, assignments, arithmetic) are performed as a function of the input size n , and ask how that count grows .
Big-O notation gives an upper bound on growth. Formally, f(n) is O(g(n)) if there are constants c > 0 and n₀ such that f(n) ≤ c · g(n) for all n ≥ n₀. In practice, two rules do most of the work:
Drop constant factors. 500n and 2n are both O(n).
Drop lower-order terms. For f(n) = 3n² + 50n + 1000, the n² term dominates as n grows. At n = 10,000 it is 300,000,000 of the 300,501,000 total operations, about 99.8%. So f(n) is O(n²).
Related notations: Ω (big-Omega) is a lower bound and Θ (big-Theta) is a tight bound (both upper and lower). These are bounds on functions. Separately, we analyze an algorithm's best case , average case , and worst case . For example, linear search is Θ(1) in its best case and Θ(n) in its worst case.
The growth classes
- Class Name Typical cause Examples
- O(1) Constant Fixed number of steps Access a[i] ; push onto a stack
- O(log n) Logarithmic Problem size halves each step Binary search; loop where i ← i * 2
- O(n) Linear One pass over the data Linear search; sum or maximum of a list
- O(n log n) Linearithmic Divide in halves and do linear work per level Merge sort; average-case quicksort
O(n²) Quadratic Nested loops over the data; comparing all pairs Selection, insertion, and bubble sort; checking every pair for duplicates
- O(2ⁿ) Exponential Trying every subset; branching recursion Checking all subsets; naive recursive Fibonacci
- O(n!) Factorial Trying every ordering Brute-force traveling salesperson; listing all permutations
- What happens when n doubles
- Class n = 1,000 n = 2,000 Effect of doubling n
- O(log n) ≈ 10 ≈ 11 Adds about one step
- O(n) 1,000 2,000 Work doubles
- O(n log n) ≈ 10,000 ≈ 22,000 Slightly more than doubles
- O(n²) 1,000,000 4,000,000 Work quadruples
- O(2ⁿ) 2¹⁰⁰⁰ 2²⁰⁰⁰ Work is squared; hopeless at this size
A related shortcut: for an exponential algorithm, adding just one item doubles the work.
Concrete growth
- n log₂ n n log₂ n n² 2ⁿ
- 4 2 8 16 16
- 16 4 64 256 65,536
- 64 6 384 4,096 ≈ 1.84 × 10¹⁹
- 1,024 10 10,240 1,048,576 ≈ 1.8 × 10³⁰⁸
- 1,000,000 ≈ 20 ≈ 2 × 10⁷ 10¹² astronomically large
At a million items, an O(n log n) sort does about 20 million basic steps, while an O(n²) sort does about a trillion, roughly 50,000 times as many.
- Reading growth from code
- Rule 1: sequential blocks add, and the largest term wins for ( int i ← 0; i < n; i ← i + 1 )
- print i
- end for
- for ( int i ← 0; i < n; i ← i + 1 )
- for ( int j ← 0; j < n; j ← j + 1 )
- print i + j
- end for
- end for
The first loop is O(n) and the nested loops are O(n²). The total is O(n + n²) = O(n²) .
Rule 2: nested loops multiply
An outer loop of n passes containing an inner loop of m passes runs the body n × m times. When m = n, that is O(n²) .
- Rule 3: dependent (triangular) loops are still quadratic int count ← 0
- for ( int i ← 1; i ≤ n; i ← i + 1 )
- for ( int j ← i; j ≤ n; j ← j + 1 )
- count ← count + 1
- end for
- end for
The inner loop runs n, then n − 1, …, down to 1 time: n(n + 1)/2 total. Dropping the constant ½ and the lower-order term leaves O(n²) .
- Rule 4: a multiplied or divided loop variable is logarithmic int p ← 1
- while ( p < n )
- p ← p * 2
- end while
p takes the values 1, 2, 4, 8, …, so the loop runs about log₂ n times: O(log n) . The same holds for a loop that halves a value until it reaches 1.
Rule 5: branching recursion is often exponential
A recursive procedure that makes two recursive calls on inputs only slightly smaller (for example, n − 1 and n − 2) builds a call tree that roughly doubles at each level, which is exponential (Section 6.3).
Space as well as time
The same notation describes memory use. Finding the maximum of a list uses O(1) extra space: one variable. Merge sort uses O(n) extra space for its temporary arrays. Recursion uses stack space proportional to its depth. ETS lists space limitations alongside time limitations (Section 5.2), so read whether a question asks about time or memory.
Common data-structure costs
- Structure Operation Typical cost
- Array Access by index O(1)
- Array Search an unsorted array O(n)
- Array Insert at the front (shift everything) O(n)
- Sorted array Binary search O(log n)
- Hash table (dictionary) Look up by key O(1) on average
- Balanced binary search tree Search, insert O(log n)