Linear Time: O(n)

Grokking Algorithm Complexity and Big-O

Ask Author

Back to course home

0% completed

Vote For New Content

Linear Time: O(n)

Table of Contents

Contents are not accessible

Linear Time Complexity $O(n)$ describes algorithms where the runtime grows directly in proportion to the input size. This means that as the input size doubles, the time taken by the algorithm also doubles.

Key Characteristics

In an algorithm with $O(n)$ time complexity:

The number of steps the algorithm takes grows linearly with the input size.
This is common in algorithms that need to examine every element of the input, like searching or filtering.

Code Example

Let’s look at an example of an $O(n)$ algorithm. This function calculates the sum of all elements in a list:

Python3

. . . .

Explanation: calculate_sum method iterates through each element of arr, adding it to total.

Why $O(n)$ ? The loop runs once for each element, so if arr has $n$ elements, the function performs $n$ additions, giving it a time complexity of $O(n)$ .

Examples of $O(n)$ operations

Iterating through each element in a list: When you need to process every item in a list, like summing numbers or finding the maximum, the time taken grows with the list length.
Searching through unsorted data: In an unsorted list, you might need to check each element to find a specific value, making the operation take $O(n)$ time.
Counting items in a collection: If you’re counting all items in a stack, queue, or similar data structure, the time taken will be proportional to the number of items.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Key Characteristics

Code Example

Examples of O(n) operations

Examples of $O(n)$ operations