Chapter 2: When Resources Have Boundaries (Time and Space Complexity)

Mr. Pallas's Cat's Warm Welcome
The first lesson of a scientist — reasoning has a cost. Before starting to compute, we need to ask: how much time will this take? How much space does it need? Like checking your provisions and pack before setting out on a journey, a good thinker always assesses the boundaries of resources first.

---

Core Question: What Structure Do We Use to Describe the World?

A week later, on a spring afternoon, warm rain drifted in from the Pearl River, gently tapping against the glass windows of the Black Stone House study. On the red-brick arched windows, raindrops traced winding paths downward, like the traces on a circuit board. Outside, fresh raindrops clung to the new leaves of Kangle Garden's banyan trees, and the kapok blossoms looked even redder in the rain. Piglet was still puzzling over the NAND gate circuits from the previous chapter, while Little Seal was organizing his historical notes on Boole.

Mr. Pallas's Cat brewed a pot of Fenghuang Dancong oolong tea, the honeyed fragrance of Chaoshan gongfu tea spreading through the room, mingling with the scent of spring rain outside and the earthy smell of the red-brick walls. Though no fire burned in the fireplace, the flue built in 1914 seemed still to hold the warmth of history.

"Last time we discussed how to represent the world," Mr. Pallas's Cat began slowly. "From the dot-dash of the telegraph to the on-off of the flashlight — we used binary logic to simplify the world."

Little Seal put down his pen, thoughtful. "Professor, I have a question. If we already can represent the world with 0 and 1, what comes next?"

Piglet looked up from his circuit board. "Yeah — like, once you have an alphabet, the next question is how to organize those letters to write an essay?"

Mr. Pallas's Cat smiled. "Great questions. That's exactly today's core issue: what structure do we use to describe the world?"

He walked to the whiteboard and wrote two words:

Time — Space

"When we describe anything," Mr. Pallas's Cat said, turning to face them, "we must consider both of these dimensions. For example, describing a book:

• Time: how many hours to read it?
• Space: how many centimeters of shelf space does it occupy?

In the world of computation, these two dimensions become time complexity and space complexity — the structures that describe how an algorithm 'occupies' time and space."

A Thought Experiment: The Universal Library — A Test of Structure

"Remember the 'Universal Library' we mentioned last time?" Mr. Pallas's Cat asked.

Piglet's eyes lit up. "Yes! The Professor said to find one specific book among all the books in the universe... how is that even possible?"

Little Seal added, "There are about 10^80 atoms in the universe. If each book..."

"Let's simplify first," Mr. Pallas's Cat interrupted with a smile. "Suppose the library has N books. You want to find one particular book — The Origin of Reasoning Science."

---

Two Kinds of Search: Brute Force and Wisdom

The Heavy Cost of Brute-Force Search

Piglet answered without thinking: "Then search one by one! Start from the first shelf in the first row."

"That's brute-force search," Mr. Pallas's Cat nodded. "Also the most intuitive method. Let's calculate how long that would take."

He wrote on the whiteboard:

Assume checking one book takes 1 second.

• 100 books: at most 100 seconds ≈ 1.7 minutes (acceptable)
• 10,000 books: at most 10,000 seconds ≈ 2.8 hours (the length of a meal)
• 1,000,000 books: at most 1,000,000 seconds ≈ 11.6 days (a short trip)
• 1,000,000,000 books: at most 31.7 years (half a lifetime)

Piglet's mouth dropped open. "And if it's all the books in the universe..."

"That's the reality," Mr. Pallas's Cat said calmly. "The efficiency of an algorithm is not an optional decoration — it is a life-or-death choice."

Mr. Pallas's Cat's Commentary
Brute-force search has a time complexity of O(n) — the number of operations is proportional to the data size n. When n is large, "proportional" can mean "impossible to complete."

Binary Search: The Art of Halving

Little Seal thought for a moment and asked: "What if the library's books are arranged in order? Say, alphabetically by title?"

Mr. Pallas's Cat's eyes lit up. "Great question! In that case we can use binary search — a much smarter strategy."

He drew a simple flowchart:

Open the middle book
    ↓
Is it the target? → Yes → Success!
    ↓ No
Is the target on the left or right?
    ↓
Discard the other half, repeat the process

"Each check halves the search range," Mr. Pallas's Cat explained. "Like folding a piece of paper in half, over and over."

Piglet quickly calculated: "For 16 books... first check leaves 8, second leaves 4, third leaves 2, fourth finds it! Only 4 checks!"

"Right," Mr. Pallas's Cat said approvingly. "100 books need only 7 checks. A billion books need only 30 checks."

He drew a comparison table on the whiteboard:

Number of Books	Brute-Force Checks	Binary Search Checks
10	10	4
100	100	7
1,000	1,000	10
1,000,000	1,000,000	20
1,000,000,000	1,000,000,000	30

Little Seal said quietly: "That gap... it's exponential. One side grows linearly, the other logarithmically."

Advanced: The Mathematical Principle of Logarithmic Time

Binary search has a time complexity of O(log₂ n), which arises from halving the problem size at each step.

Mathematically, let the initial size be n; after k halvings, the size becomes 1:

$$\frac{n}{2^k}=1\Rightarrow 2^k=n\Rightarrow k={\log }_{2}n$$

Here, log₂ n grows extremely slowly:

• log₂ 10 ≈ 3.32
• log₂ 100 ≈ 6.64
• log₂ 1,000,000 ≈ 19.93
• log₂ 1,000,000,000 ≈ 29.90

This "slow growth" is one of the holy grails of algorithm design. Many efficient algorithms (balanced binary search trees, the expected complexity of quicksort) all embody the logarithmic idea.

---

Mental Model: Resource Awareness — Structures for Describing the World

Mr. Pallas's Cat walked to the window and gazed at the rain outside. "Let's return to our original question: what structure do we use to describe the world?"

He turned to face them, pointing at the two words already written on the whiteboard:

Time — Space

"That's the answer," Mr. Pallas's Cat said. "In the world of computation, we describe everything using time structures and space structures. This leads to today's most important mental model: resource awareness."

"Computation is not magic happening in a vacuum. It consumes two precious resources: time and space."

Time Complexity: The Order of Growth

"The number of search operations we just discussed is time complexity," said Mr. Pallas's Cat. "But computer scientists don't care about 'exactly how many seconds.' They care about the trend of growth."

He wrote a series of symbols on the whiteboard:

• O(1): constant time. Regardless of data size, the operation takes the same time
• O(log n): logarithmic time. Binary search — halving each time
• O(n): linear time. Brute-force search — proportional to data size
• O(n log n): linearithmic time. Many efficient sorting algorithms
• O(n²): quadratic time. Nested loops comparing all pairs
• O(2ⁿ): exponential time. Certain combinatorial problems — catastrophic growth

"This is Big O notation," Mr. Pallas's Cat explained. "It describes the asymptotic behavior of an algorithm in the worst case."

Piglet pointed at O(2ⁿ) and asked, "How terrifying is this 'exponential time'?"

Mr. Pallas's Cat drew a simple table:

n	O(n)	O(n²)	O(2ⁿ)
10	10	100	1,024
20	20	400	1,048,576
30	30	900	1,073,741,824
40	40	1,600	~1.1 trillion
50	50	2,500	~11 quadrillion

"See that?" Mr. Pallas's Cat said. "When n = 50, O(2ⁿ) is already an astronomical number. This is why we say problems of exponential complexity are often practically unsolvable."

Space Complexity: The Cost of Memory

Little Seal mused: "Besides time, storing information also requires space."

"Exactly," Mr. Pallas's Cat nodded. "That's space complexity."

He gave an example: "Suppose you need to sort a deck of cards. There are two approaches:

1. In-place sorting: move the cards around on the tabletop, almost no extra space needed (O(1) space)
2. Not-in-place sorting: need another empty table for intermediate results (O(n) space)

"Space and time often require trade-offs," Mr. Pallas's Cat continued. "Sometimes we can trade more space for faster time — 'space for time.' Conversely, on memory-constrained devices, we may choose slower but space-efficient algorithms."

Advanced: The History and Philosophy of Big O Notation

Big O notation was introduced by the German mathematician Paul Bachmann in 1894 and later popularized by Edmund Landau. The symbol O comes from the German word "Ordnung" (order), describing the order of growth of a function.

The core philosophy of Big O notation is abstraction and simplification:

1. Ignore constant factors: 3n and 100n are both O(n)
2. Ignore lower-order terms: n² + 1000n + 50000 is O(n²)
3. Focus on the worst case: providing guarantees for algorithm performance

This simplification is not "imprecision" — it is purposeful abstraction. Just as a map doesn't need to be at a 1:1 scale, complexity analysis doesn't need to be precise down to the clock cycle.

It's worth considering: Big O notation reflects asymptotic behavior. For small-scale data, constant factors may matter more. This is why sometimes a "theoretically superior" algorithm performs worse in practice than a simple one.

---

Orthogonal Computation Graphs: Seeing the Spectrum of Complexity

Mr. Pallas's Cat turned on the projector, and a neat computation graph appeared on the screen.

"This is the orthogonal computation graph for different complexity classes," Mr. Pallas's Cat said, pointing. "From left to right: input size n passes through different complexity classes, producing different growth curves."

Piglet stared at the graph. "O(1) to constant, O(log n) to logarithmic... and this O(2ⁿ) to exponential — the line suddenly shoots up!"

"That's the key," Mr. Pallas's Cat said. "Exponential growth is like a runaway horse — insignificant at first, but it blows past every limit in the blink of an eye."

Little Seal examined the layered structure of the graph carefully. "Professor, the design of this graph... each complexity class is on the same layer, and the output curves are also on the same layer. Very orderly."

"That's the power of orthogonal computation graphs," Mr. Pallas's Cat smiled. "They tell us in visual language: complexity is not a vague feeling, but clearly separable categories."

Advanced: Rigorous Definitions of Complexity Classes

In computer science, complexity classes have strict formal definitions:

• P (Polynomial time): problems solvable by an algorithm in polynomial time
• NP (Nondeterministic Polynomial time): problems whose solutions can be verified in polynomial time
• EXP (Exponential time): problems requiring exponential time
• LOGSPACE: problems requiring only logarithmic space

The famous P vs NP problem (one of the seven Millennium Prize Problems) asks: does P equal NP? If so, then all problems whose solutions are easy to verify are also easy to solve.

The prevailing consensus is that P ≠ NP, meaning some problems are inherently harder than others. The discovery of this "intrinsic difficulty" is one of the deepest insights of 20th-century theoretical computer science.

---

Real-World Complexity Dilemmas

Case 1: The Butterfly Effect of Social Networks

Piglet pulled out his phone. "How does something like WeChat find 'people you might know'?"

"A naive algorithm would be O(n²)," Mr. Pallas's Cat said. "Suppose you have 100 friends, and each friend has 100 friends. To find common friends, you'd need 100 × 100 = 10,000 comparisons."

He paused. "But if each person has 1,000 friends? A million operations. Real social networks have hundreds of millions of users — O(n²) is simply infeasible."

"So what do they do?" Piglet asked.

"Real systems use approximation algorithms, indexing techniques, and distributed computing," Mr. Pallas's Cat said. "Sacrificing a bit of precision for feasibility. This is a common compromise in engineering."

Case 2: The Maze of Map Navigation

Little Seal opened a map app. "How does navigation software find the shortest path?"

"The simplest brute-force search is O(n!)," Mr. Pallas's Cat said. "n is the number of intersections. For a map with 20 intersections, 20! ≈ 2.4 × 10¹⁸ possible paths."

Piglet gasped. "That... you couldn't finish computing before the universe ends."

"That's why we need smarter algorithms," Mr. Pallas's Cat said. "Like Dijkstra's algorithm (O(n²)) or the A* algorithm (which uses a heuristic function to guide the search). These algorithms don't guarantee to find all possible paths, but they guarantee to find the optimal or near-optimal solution within feasible time."

Mr. Pallas's Cat's Commentary
Real-world problems often require finding a balance between the ideal and the feasible. The perfect solution may not exist, or may be too costly. A good algorithm designer understands: sometimes, a good-enough solution is the best solution.

---

The Eternal Dance of Space and Time — Structural Interactions in Describing the World

Mr. Pallas's Cat returned to the whiteboard and drew a pair of axes.

"Let's return to our original question," he said. "What structure do we use to describe the world? The answer: time and space. But these two are not isolated — they are interconnected, mutually constraining."

He pointed at the axes: "Time and space are like two ends of a scale. Adding to one often reduces the other. This is how the two fundamental structures for describing the world interact."

Space for Time: Lookup Tables

"Take computing Fibonacci numbers," Mr. Pallas's Cat offered as an example. "The naive recursive approach is O(2ⁿ) — agonizingly slow. But if we use an array to store already-computed results —"

He wrote on the whiteboard:

fib = [0, 1]  # storage space
for i in range(2, n+1):
    fib[i] = fib[i-1] + fib[i-2]  # lookup instead of recomputing

" — it becomes O(n) time, O(n) space. A little storage space buys an enormous time saving."

Time for Space: Stream Processing

"Conversely," Mr. Pallas's Cat continued, "on memory-constrained devices (like embedded systems), we might choose stream processing — processing a small chunk of data at a time. It may take more time, but saves significant space."

Little Seal mused: "It's like when reading — do you buy the book (occupying shelf space) or borrow it from the library each time (spending time)?"

"Great analogy!" Mr. Pallas's Cat praised. "The essence of resource allocation is trade-off. There's no free lunch — only optimization choices based on constraints."

Advanced: The Mathematical Form of Time-Space Trade-offs

Time-space trade-offs can be formalized as time-space trade-off theorems. For many problems, there exists a continuous spectrum:

Let T be the time and S the space needed to solve a problem; typically:

$$T\cdot S\ge f(n)$$

where f(n) is the inherent complexity function of the problem.

For example, in sorting:

• Quicksort: expected O(n log n) time, O(log n) space (recursion stack)
• Mergesort: O(n log n) time, O(n) space (needs auxiliary array)
• Heapsort: O(n log n) time, O(1) space (in-place sorting)

The choice of algorithm depends on the specific scenario: data scale, memory constraints, whether stability is needed, etc. There is no absolute best — only the most suitable.

---

Key Takeaways

Mr. Pallas's Cat's Summary: Two Structures for Describing the World
When we use computation to describe the world, time and space are our most fundamental descriptive frameworks.

1. Reasoning has a cost: time and space are hard constraints on computation; a good thinker first assesses resource boundaries
2. Complexity classes: O(1), O(log n), O(n), O(n²), O(2ⁿ) represent different orders of growth — the differences can be astronomical
3. The Big O philosophy: focus on asymptotic trends rather than exact numbers; purposeful abstraction
4. Time-space trade-offs: time and space can often be exchanged; the choice depends on specific constraints
5. Feasibility thinking: real problems often require balancing the ideal and the feasible — perfectionism can be the enemy of efficiency

---

Code Practice: Implementing Complexity Analysis in Python

"Let's use code to understand the differences between various time complexities," said Mr. Pallas's Cat. "From the intuitive to the abstract, from concrete operations to asymptotic analysis."

Implementing Algorithms of Different Time Complexities

import time
import matplotlib.pyplot as plt

# O(1) Constant time complexity
def constant_time_operation(n):
    """Constant-time operation: regardless of input size, takes the same time
    
    Parameters:
        n: input size
    
    Returns:
        always returns 42 (example operation)
    """
    return 42  # this operation takes the same time no matter how large n is

# O(log n) Logarithmic time complexity
def binary_search_iterative(arr, target):
    """Binary search: halves the search space each time
    
    Parameters:
        arr: a sorted array
        target: the value to search for
    
    Returns:
        index of target in arr, or -1 if not found
    """
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2  # prevents overflow
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1  # search the right half
        else:
            right = mid - 1  # search the left half
    return -1

# O(n) Linear time complexity
def linear_search(arr, target):
    """Linear search: checks each element one by one
    
    Parameters:
        arr: an array
        target: the value to search for
    
    Returns:
        index of target in arr, or -1 if not found
    """
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

# O(n log n) Linearithmic time complexity
def merge_sort(arr):
    """Mergesort: a divide-and-conquer sorting algorithm
    
    Parameters:
        arr: the array to be sorted
    
    Returns:
        the sorted array
    """
    if len(arr) <= 1:
        return arr
    
    # Divide: split the array into two halves
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    
    # Conquer: merge the two sorted arrays
    return merge(left_half, right_half)

def merge(left, right):
    """Merge two sorted arrays"""
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # Append remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# O(n²) Quadratic time complexity
def bubble_sort(arr):
    """Bubble sort: repeatedly compares adjacent elements
    
    Parameters:
        arr: the array to be sorted
    
    Returns:
        the sorted array
    """
    n = len(arr)
    for i in range(n):
        # the last i elements are already sorted
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # swap
    return arr

# O(2ⁿ) Exponential time complexity
def fibonacci_recursive(n):
    """Recursively compute Fibonacci numbers (exponential time example)
    
    Parameters:
        n: the position in the Fibonacci sequence
    
    Returns:
        the nth Fibonacci number
    """
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# Improved O(2ⁿ): dynamic programming (covered in detail in the next chapter)
def fibonacci_dp(n):
    """Compute Fibonacci numbers using dynamic programming (linear time)
    
    Parameters:
        n: the position in the Fibonacci sequence
    
    Returns:
        the nth Fibonacci number
    """
    if n <= 1:
        return n
    
    fib = [0] * (n + 1)
    fib[1] = 1
    
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    
    return fib[n]

Time Complexity Comparison Experiment

def measure_time_complexity():
    """Measure the actual running time of algorithms with different time complexities"""
    sizes = [10, 100, 1000, 10000]
    
    results = {}
    
    for size in sizes:
        # Prepare test data
        sorted_arr = list(range(size))
        unsorted_arr = list(range(size, 0, -1))  # reverse order
        
        # O(1) - constant time
        start = time.time()
        constant_time_operation(size)
        o1_time = time.time() - start
        
        # O(log n) - logarithmic time (search for the middle value in a sorted array)
        target = size // 2
        start = time.time()
        binary_search_iterative(sorted_arr, target)
        olog_time = time.time() - start
        
        # O(n) - linear time (search for the last element)
        start = time.time()
        linear_search(sorted_arr, size - 1)
        on_time = time.time() - start
        
        # O(n log n) - linearithmic time (sort a reverse-ordered array)
        start = time.time()
        merge_sort(unsorted_arr[:])  # use a copy to avoid in-place modification
        onlogn_time = time.time() - start
        
        # O(n²) - quadratic time (sort a reverse-ordered array)
        # Note: for large n, bubble_sort will be very slow, so keep it small
        if size <= 1000:
            start = time.time()
            bubble_sort(unsorted_arr[:])
            on2_time = time.time() - start
        else:
            on2_time = None  # too large, skip
            
        # O(2ⁿ) - exponential time (compute Fibonacci numbers)
        # Note: exponential time grows too fast, only test small n
        if size <= 30:
            start = time.time()
            fibonacci_recursive(size)
            o2n_time = time.time() - start
        else:
            o2n_time = None
        
        results[size] = {
            'O(1)': o1_time,
            'O(log n)': olog_time,
            'O(n)': on_time,
            'O(n log n)': onlogn_time,
            'O(n²)': on2_time,
            'O(2ⁿ)': o2n_time
        }
        
        print(f"\nInput size n = {size}:")
        for complexity, t in results[size].items():
            if t is not None:
                print(f"  {complexity}: {t:.6f} seconds")
            else:
                print(f"  {complexity}: too large, skipped")
    
    return results

# Run the experiment
print("Time Complexity Comparison Experiment")
print("=" * 50)
results = measure_time_complexity()

Complexity Visualization Tool

def plot_complexity_growth():
    """Visualize the growth trends of different time complexities"""
    n_values = list(range(1, 101))
    
    # Compute the growth of different complexity functions
    constant = [1] * len(n_values)
    logarithmic = [np.log2(n) for n in n_values]
    linear = n_values
    linearithmic = [n * np.log2(n) for n in n_values]
    quadratic = [n ** 2 for n in n_values]
    exponential = [2 ** n for n in n_values]
    
    plt.figure(figsize=(12, 8))
    
    plt.plot(n_values, constant, label='O(1) - Constant', linewidth=2)
    plt.plot(n_values, logarithmic, label='O(log n) - Logarithmic', linewidth=2)
    plt.plot(n_values, linear, label='O(n) - Linear', linewidth=2)
    plt.plot(n_values, linearithmic, label='O(n log n) - Linearithmic', linewidth=2)
    plt.plot(n_values, quadratic, label='O(n²) - Quadratic', linewidth=2)
    # Exponential grows too fast; show only a small range separately
    plt.plot(n_values[:10], exponential[:10], label='O(2ⁿ) - Exponential (n≤10)', linewidth=2)
    
    plt.xlabel('Problem Size (n)', fontsize=12)
    plt.ylabel('Time Complexity Growth', fontsize=12)
    plt.title('Growth Trends of Different Time Complexities', fontsize=14)
    plt.legend()
    plt.grid(True, alpha=0.3)
    plt.yscale('log')  # use logarithmic scale to better show differences
    
    print("Complexity growth trend chart generated. Key observations:")
    print("1. O(1) and O(log n) grow the slowest — suitable for large-scale problems")
    print("2. O(n) and O(n log n) are the ideal choices for most practical problems")
    print("3. O(n²) slows down dramatically at large scales")
    print("4. O(2ⁿ) grows extremely fast even at small scales — must be avoided")

# Note: requires numpy and matplotlib
try:
    import numpy as np
    plot_complexity_growth()
except ImportError:
    print("\nNote: to run the visualization code, install numpy and matplotlib first")
    print("Installation command: pip install numpy matplotlib")

print("\n" + "=" * 50)
print("Mr. Pallas's Cat's Complexity Reflection Questions:")
print("1. If n = 1,000,000, how long would an O(n²) algorithm take? Assume 1 nanosecond per step")
print("2. How much faster is binary search (O(log n)) than linear search (O(n))? What about when n = 1 billion?")
print("3. Why is mergesort (O(n log n)) more suitable for large-scale data than bubble sort (O(n²))?")

"Through this code," Mr. Pallas's Cat summarized, "we not only understand the concepts of different time complexities, but also learn resource awareness — before starting to code, first ask: how much time will this take? How much space does it need? This is the first step in scientific reasoning."

---

Mr. Pallas's Cat's Reflection Questions

Hands-On Exploration (for Piglet)

1. Complexity experiment: Write two programs: one O(n²) nested loop and one O(n) single loop. Test their running time for n = 1000, 10000, 100000. Feel the exponential difference.

2. Algorithm design: Design an algorithm to "find the maximum value in an array." First write an O(n²) version (compare all pairs), then improve it to O(n) (traverse once). Experience the power of algorithmic improvement.

3. Real-world observation: Observe the software or devices around you (elevators, traffic lights, search engines) and guess what time complexity their algorithms might have. Why were those choices made?

Historical Investigation (for Little Seal)

1. Tracing the symbol: Research the history of Big O notation. Why the letter O? What contributions did Paul Bachmann and Edmund Landau each make?

2. Problem evolution: Investigate the origins and development of the "P vs NP problem." Why is this problem so important? What progress and conjectures currently exist?

3. Intellectual lineage: How did complexity theory develop from Turing's theory of computability? What deep connections exist between the two?

Integrated Reflection

1. Ethical dilemma: Suppose you are designing a medical diagnosis system. One algorithm is 99.9% accurate but takes 10 minutes; another is 99% accurate but takes only 1 second. How do you choose? Why?

2. Limit challenge: If Moore's Law continues to hold (computing power doubles every 18 months), can it solve exponentially complex problems? Prove your view mathematically.

3. Creative exercise: Design a "complexity fable" — explain the differences among O(1), O(log n), O(n), O(n²), and O(2ⁿ) in story form. (Hint: compare them to vehicles of different speeds.)

4. Future imagination: Quantum computing claims it can solve certain exponential-complexity problems (like factoring large numbers). Research how this is possible. What impact would this have on existing complexity theory?

---

Coming Up Next

The rain gradually stopped, and the golden light of the setting sun broke through the clouds, scattering shattered gold across the surface of the Pearl River. The dusk over Kangle Garden was gentle, and the kapok blossoms looked especially serene in the evening glow.

"Today we started from the question of 'the structures we use to describe the world,'" Mr. Pallas's Cat said, tidying up the gongfu tea set. "We explored time and space as the fundamental frameworks of computation, saw the cost of reasoning, and the existence of resource boundaries."

Piglet was still fiddling with the timer, testing the actual running times of different algorithms, the glow of the computer screen reflected on his focused face.

Little Seal closed his notebook and said quietly, "Professor, what if there are some problems that — no matter how clever we are, no matter how fast computers become — are inherently impossible to solve within a reasonable time?"

Mr. Pallas's Cat's movements paused, the teapot suspended in midair.

"You've touched on something crucial," he said slowly. "In the next chapter, we will explore exactly this question: some problems cannot be solved even by the most powerful computer."

Piglet's head snapped up. "What? There are problems computers can't solve?"

"Not 'can't solve now,'" Mr. Pallas's Cat corrected. "But can never solve. This is the essential boundary of computation."

Little Seal's eyes lit up. "Turing's halting problem?"

"Yes," Mr. Pallas's Cat smiled. "We will explore the limits of computability — what is the ultimate boundary of computation."

Outside the window, the last ray of sunlight disappeared below the horizon, and ships on the distant Pearl River lit their lights. In the study of the Black Stone House, the shadows of the three thinkers were stretched long by the lamplight, cast upon the red-brick wall.

---

Piglet's note: The test results shocked me! The O(n²) algorithm took 5 seconds for n = 10000, while the O(n) algorithm took only 0.005 seconds. A 1000x difference! The theoretical difference is so real in practice.

Little Seal's note: I read about the history of Big O and discovered it was first used in number theory for the study of prime distribution. The various branches of mathematics are always connected in such marvelous ways.

Mr. Pallas's Cat's closing words: Remember, the first thing a good algorithm designer must have is resource awareness. Before you start coding, ask: how much time will this take? How much space does it need? But more importantly: does this problem itself have an efficient solution? We'll take it slow — understanding is what matters most.