Course contentsShow
← Computer Science
Lesson 273 of 2,8727. Introduction to Complexity AnalysisFree lesson

Input Size as a Variable

Understanding how runtime depends on input size n and expressing runtime as a function of n.

Input Size as a Variable

What you'll learn: How to express an algorithm's runtime as a mathematical function that depends on how much data it processes.


When analyzing runtime, we need a way to describe how performance changes as the amount of input grows. This is where input size comes in—we represent it with the variable n.

Why Input Size Matters

Imagine counting all the books on a shelf. If you have 10 books, it takes a certain amount of time. If you have 1,000 books, it takes much longer. The number of books is your input size, and runtime clearly depends on it.

In runtime analysis, we stopped counting exact milliseconds (which vary by computer) and started counting primitive operations. Now we express how many operations as a formula using n to represent input size.

Expressing Runtime as f(n)

When we say "runtime is a function of n," we mean: the number of operations depends on n.

For example:

  • Linear search through an array: In the worst case, you check every element. If the array has n elements, you perform roughly n comparisons. Runtime = f(n) = n
  • Nested loop processing pairs: If you compare every element with every other element, you do roughly n × n operations. Runtime = f(n) = n²
  • Array access: Reading one element at index 0 takes constant time, no matter how big the array is. Runtime = f(n) = 1 (constant, independent of n)

The variable n lets us compare algorithms fairly: "This one does 5n operations, that one does n² operations—which scales better as n grows?"


Key Takeaway:
Runtime analysis expresses the number of operations as a function of input size n, allowing us to predict and compare performance as data scales.