Linear Time Complexity

Linear time complexity means that the time taken by an algorithm increases directly in proportion to the size of the input. In other words, if you double the size of the input, the algorithm will take twice as long to complete.

An algorithm has a time complexity of O(n) when it needs to perform a single operation for each element in the input data. This type of algorithm is common when you need to process or iterate through all elements of a list or array exactly once.

Example

Problem: Finding an Element in an Unsorted List

Suppose you have an unsorted list of numbers:

[4, 2, 7, 1, 9, 3]

Let's say you want to find whether the number 9 exists in the list.

How Linear Search Works:

1. Step 1: Start at the first element.
   • Check 4 → Not 9
2. Step 2: Move to the next element.
   • Check 2 → Not 9
3. Step 3: Move to the next element.
   • Check 7 → Not 9
4. Step 4: Move to the next element.
   • Check 1 → Not 9
5. Step 5: Move to the next element.
   • Check 9 → Found it!

In the worst case, you may have to check every element in the list (like if the element is at the last position or not present at all).

Why is Linear Search O(n)?

• The algorithm checks each element one by one.
• For a list of size ( n ), it may take up to ( n ) comparisons to find the target element.
• If the list size increases, the number of operations grows linearly.

Real-Life Analogy

Imagine you have a stack of 100 sheets of paper with different names written on each. If you're trying to find a specific name, you would have to look at each sheet one by one until you find the right name. If the name is on the 100th sheet, you will need to check all 100 sheets.

In this scenario, if the number of sheets doubles to 200, the time it takes to find the specific name also doubles, making it O(n).