Skip to main content

Feasibility Is About Growth

What This Concept Is​

In computer science, "can we do this?" often really means "how do time and memory grow as the input grows?" Complexity thinking ignores minor constants and focuses on dominant growth: linear, quadratic, logarithmic, exponential, and so on.

Why It Matters Here​

Many beginners think a problem is practical as long as the computer is fast enough. That fails quickly. Some approaches remain reasonable as data grows. Others explode. This is why algorithm design, data choice, and machine behavior matter long before micro-optimizations.

Concrete Example​

Selection sort grows roughly like n^2. If the input becomes ten times larger, the work becomes about one hundred times larger.

By contrast, an O(n log n) sort grows much more gently. For large inputs, that gap becomes the difference between seconds and hours.

The same idea appears in harder problems:

  • O(1) feels instant
  • O(n) scales with input size
  • O(n^2) gets painful fast
  • O(2^n) becomes unrealistic surprisingly early

Memory matters too. Even if an algorithm's logic is fine, poor memory access or too much duplicated work can make it slow in practice.

Common Confusion / Misconception​

Big O is not a stopwatch prediction and it is not "the exact runtime." It is a growth-class summary. Another mistake is caring only about CPU speed while ignoring memory cost, caching, and data movement.

How To Use It​

When comparing approaches, ask:

  1. What is the input size?
  2. Which operation repeats most?
  3. What term dominates as the input grows?
  4. Does the approach also consume a lot of memory?
  5. Is the problem size small enough that a theoretically worse method is still acceptable?

Use growth thinking as an early filter. It saves you from polishing an impossible approach.

Check Yourself​

  1. Why can a tiny implementation detail matter less than the growth class?
  2. Why is O(2^n) considered dangerous even on powerful hardware?
  3. What does it mean to say one term "dominates" the others?

Mini Drill or Application​

Pick two of these pairs and explain which one scales better and why:

  • O(n) vs O(n^2)
  • O(n^2) vs O(n log n)
  • O(n^3) vs O(2^n)

Then write one real-world scenario where memory cost could matter as much as CPU cost, such as image processing, browser tabs, or caching.

Read This Only If Stuck​