Linear Time refers to an algorithm whose running time grows proportionally with the size of the input.
If the input doubles, the time taken also roughly doubles.
In algorithm analysis, this is written as:
O(n)
Linear time is common and efficient for many real-world problems.
An algorithm runs in linear time when it must process each element of the input at least once.
For example:
- Scanning a list to find a value
- Counting elements in an array
- Printing all items in a collection
If there are n items, the algorithm performs about n steps.
def find_max(arr):
max_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
return max_valThe loop checks every element once → O(n) time.
def count_even(numbers):
count = 0
for n in numbers:
if n % 2 == 0:
count += 1
return countEach element is inspected once, so runtime grows linearly.
def linear_search(arr, target):
for value in arr:
if value == target:
return True
return FalseWorst case: the algorithm checks all elements → O(n).
| Complexity | Meaning |
|---|---|
| O(1) | Constant time |
| O(log n) | Logarithmic time |
| O(n) | Linear time |
| O(n log n) | Linearithmic time |
| O(n²) | Quadratic time |
Linear time scales well for most applications and is often unavoidable when every element must be examined.
- Efficient for moderate and large datasets
- Easy to implement and understand
- Predictable performance
- Works well when full data traversal is required
- Slower than constant or logarithmic time
- May become expensive for extremely large datasets
- Not ideal for repeated searches on static data (use indexing or hashing instead)
Linear time operations appear when:
- Iterating through arrays or lists
- Reading files line by line
- Summing values in a dataset
- Performing linear search
- Filtering elements based on conditions
These operations are fundamental in programming and data processing.
Linear time complexity O(n) means runtime increases directly with input size. It represents efficient performance for tasks that must inspect each element and forms the foundation of many algorithms.