Algorithm Analysis and Sequential Search

In this article Learn algorithm analysis through time and space complexity, and understand how sequential (linear) search works with examples, advantages, disadvantages, and complexities.

Algorithm Analysis and Sequential Search

Algorithm analysis refers to measuring how much time an algorithm takes (Time Complexity) and how much memory it uses (Space Complexity).

Objectives of Algorithm Analysis

• To determine how efficient an algorithm is
• To check whether it is the best solution to the problem
• To compare different algorithms
• To understand how an algorithm behaves with large inputs

Types of Algorithm Analysis

Time Analysis

The time taken by an algorithm depends on the size of the input.
We measure this time using Asymptotic Notations:

• O (Big-O) → Worst-case time
• Ω (Omega) → Best-case time
• Θ (Theta) → Average-case or exact time

Space Analysis

Space analysis determines how much memory is required for variables, arrays, stacks, or recursion during the execution of an algorithm.

Examples:

• Variables → Constant space
• Arrays → Linear space (O(n))
• Recursion → Uses stack memory

Why is Algorithm Analysis Needed?

• To compare different algorithms
• To identify which algorithm is suitable for large datasets
• To understand algorithm performance independent of hardware
• To estimate performance even before implementation
• To design fast, efficient, and optimized software

Sequential Search (Linear Search)

Sequential Search (or Linear Search) means checking each element in a list one by one until the desired value is found.
It is the simplest searching technique.

How Sequential Search Works

Each element of the array/list is checked sequentially:

1. Check the first element
2. If it matches the target → Search successful
3. If not → Check the next element
4. Continue until the last element
5. If the element is not found → Return “Not Found”

Algorithm for Sequential Search

Step 1: Read array A of size n and target element x
Step 2: For i = 0 to n – 1
If   A[i] == x: Return i
Step 3: If not found: Return -1

Example

Array: [10, 25, 30, 45, 50]
Target: 45

Checking order:

• 10 → No
• 25 → No
• 30 → No
• 45 → Yes → Found at index 3

Time Complexity of Sequential Search

1. Best Case: Ω(1)
   Target is the first element
   → Only 1 comparison
2. Worst Case: O(n)
   Target is the last element or not present
   → All elements are checked
3. Average Case: Θ(n)
   Target is usually in the middle
   → ~n/2 comparisons ≈ Θ(n)

Space Complexity

Sequential Search uses only a few variables.
Space Complexity: O(1) (constant space)

Advantages of Sequential Search

• Very simple and easy to understand
• Works on any type of dataset
• Does not require the list to be sorted
• Performs well on small datasets

Disadvantages of Sequential Search

• Very slow for large datasets
• Every element must be checked
• O(n) time can be inefficient
• Less efficient compared to Binary Search

When is Sequential Search Used?

• When the list is small
• When the data is unsorted
• When a simple implementation is required
• When low memory usage is necessary

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1