Measuring Efficiency: Time and Space

In the previous chapter we saw that structure choices affect speed.

Now we need language to measure that effect.

---

Two Core Metrics

When evaluating an algorithm, we usually track:

• Time: how runtime grows as input size grows
• Space: how extra memory usage grows

The key word is growth, not exact milliseconds.

---

Why Growth Matters

Exact runtime depends on hardware and implementation details.

But growth behavior is stable and useful for comparison.

If input size doubles, does work double? Triple? Stay similar?

That is the heart of complexity analysis.

---

Big-O Intuition

Big-O describes how work scales with input size n.

Common growth patterns:

• O(1) constant
• O(log n) slowly growing
• O(n) linear
• O(n log n) efficient for many sorting tasks
• O(n^2) often too slow at large scale

No heavy math required here. Think in terms of trend.

---

Linear Search vs Binary Search

Linear Search

Check items one by one.

Worst-case behavior is O(n).

Binary Search

On sorted data, repeatedly cut search space in half.

Worst-case behavior is O(log n).

graph LR
  A[Start with n items] --> B[Linear: check one by one]
  A --> C[Binary: halve each step]

For very large n, this difference is dramatic.

---

Time vs Space Tradeoff

Sometimes we use more memory to reduce runtime.

Example: caching previous results can speed repeated computations.

So the best choice depends on system constraints:

• memory budget
• latency requirements
• workload shape

---

Key Ideas to Remember

• Efficiency is about growth as input size increases.
• Time complexity and space complexity are both important.
• Big-O is a model for comparing growth trends.
• O(log n) often scales better than O(n) for search.
• Faster runtime may require extra memory.

---

What Comes Next

With efficiency intuition in place, we can start with the most fundamental structure:

arrays and indexed storage.