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

O(n): Linear Time

Analyzing algorithms that process each element once, like linear search or single-pass array traversals.

O(n): Linear Time

You'll learn what linear time complexity means and how to recognize algorithms that process each element exactly once.

The Core Idea

An algorithm runs in O(n) time when its number of operations grows directly proportional to the input size. If you double the input, you roughly double the running time. If you have 10 elements, you do ~10 operations. With 100 elements, ~100 operations.

Think of it like reading a book page-by-page: to read a 200-page book takes twice as long as reading a 100-page book. You process each page once, linearly.

Common Linear Time Patterns

Single-pass array traversals are the classic example:

for i from 0 to n-1:
    process array[i]

This loop visits each element exactly once, performing constant-time work per element. Total operations: n × O(1) = O(n).

Examples from your previous lessons:

  • Linear search: checking each element until you find your target (or reach the end)
  • Finding max/min: scanning through all elements once to track the largest or smallest
  • Array reversal: visiting each element once to swap positions
  • String traversal: processing each character in a string one time

Why It Matters

Linear time is often the best you can do when you must examine every element. You can't find the maximum value without looking at all the numbers, right? O(n) represents this necessary work.

Linear time scales predictably and reasonably well—much better than quadratic O(n²) from nested loops you've analyzed before.

Key Takeaway: O(n) linear time means your algorithm processes each input element once, making the runtime directly proportional to input size—a common and efficient pattern for single-pass operations.