Sequential Search — Complexity

Sequential Search (Linear Search) is a method that checks each element one by one until the target is found or the list ends.

Time Complexity:

• Best Case: $O(1)$ — element found at the first position
• Worst Case: $O(n)$ — element found at the last position or not present
• Average Case: $O(n)$

Space Complexity: $O(1)$ — no extra space is used (in-place search)

Master Theorem — Rules for Finding Asymptotic Bounds

The Master Theorem provides a direct solution for recurrences of the form: $$T(n) = aT\left(\frac{n}{b}\right) + f(n)$$ where $a \geq 1$, $b > 1$, and $f(n)$ is an asymptotically positive function.

Let $c_{crit} = \log_b a$, then the three cases are:

Case I: If $f(n) = O(n^c)$ where $c < \log_b a$, then:

$$T(n) = \Theta(n^{\log_b a})$$

Case II: If $f(n) = \Theta(n^c)$ where $c = \log_b a$, then:

$$T(n) = \Theta(n^{\log_b a} \cdot \log n)$$

Case III: If $f(n) = \Omega(n^c)$ where $c > \log_b a$, and if $a \cdot f\left(\frac{n}{b}\right) \leq k \cdot f(n)$ for some $k < 1$ (regularity condition), then:

$$T(n) = \Theta(f(n))$$

Conclusion: Sequential search has linear time complexity, while the Master Theorem efficiently determines the asymptotic bound of divide-and-conquer recurrences by comparing $f(n)$ with $n^{\log_b a}$.