Sequential search is also known as linear search. Linear search is a simple searching algorithm that sequentially checks each element in a data structure until a match is found or the entire structure has been traversed. It works for both sorted and unsorted data structures.

Here's an explanation of the linear search algorithm:

1. Start at the beginning of the data structure.

2. Compare the target value with the current element.

3. If the target matches the current element, return the index of the element.

4. If the target does not match the current element, move to the next element in the data structure.

5. Repeat steps 2-4 until the target is found or the end of the data structure is reached.

6. If the target is not found after traversing the entire data structure, return a value indicating the target was not found.

Here's an example implementation of linear search in C:

#include <stdio.h>

int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // Target found at index i
        }
    }
    return -1; // Target not found
}

int main() {
    int arr[] = {10, 25, 7, 14, 31};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 14;

    int result = linearSearch(arr, size, target);
    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found\n");
    }

    return 0;
}

In this example, the `linearSearch` function performs the linear search algorithm on the given array. It takes the array, the size of the array, and the target value as inputs. The function iterates through the array, comparing each element with the target value. If a match is found, the function returns the index of the element. If the target is not found after traversing the entire array, the function returns -1. In the `main` function, we create an array, specify the target value, and call the `linearSearch` function to search for the target. The result is then printed based on whether the target was found or not.

The Output will be:

Element found at index 3

As you can see, the linear search algorithm successfully finds the target element at index 3 in the given array.

Time complexity

The time complexity of linear search in DAA (Design and Analysis of Algorithms) is O(n), where "n" is the number of elements in the input list or array.

Linear search is a simple algorithm that sequentially checks each element in the list until a match is found or the entire list is traversed. It starts from the first element and compares it with the target element. If a match is found, the search is successful. Otherwise, it moves on to the next element and repeats the process until a match is found or the end of the list is reached.

In the worst-case scenario, the target element may be located at the end of the list or may not be present at all, resulting in the need to traverse all n elements. Therefore, the time complexity of linear search is O(n) since the number of comparisons or iterations grows linearly with the size of the input.

Space Complexity

The space complexity of linear search in DAA is O(1), which means it requires constant space regardless of the size of the input.

Linear search only requires a few variables to perform the search, such as the target element, the current element being checked, and some loop control variables. These variables occupy a constant amount of space, regardless of the size of the input list.

The algorithm does not require any additional data structures or memory allocations that depend on the input size. Hence, the space complexity of linear search is considered constant or O(1).

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc