Understanding the Basics of Linear Search

This algorithm searches for an element in an array sequentially, one by one, until either the element is found or the end of the array is reached

• We start by taking the input array arr[] and the element to be searched x.

• We initialize a variable n to store the length of the array.

• We then traverse through each element of the array using a loop, starting from index 0 to n-1.

• At each iteration, we check if the current element of the array is equal to x. If it is, we return the index of that element.

• If we traverse the entire array without finding x, we return -1 to indicate that x is not present in the array.

  •   def linear_search(arr, x):
          n = len(arr)
          # Looping through all elements in the array
          for i from 0 to n-1:
              # If the current element is equal to x, return its index
              if arr[i] equals x:
                  return i
          # If x is not present in the array, return -1
          return -1
    

    Time Complexity:

    In the worst-case scenario, the linear search algorithm requires traversing the entire array to locate the target element, resulting in a time complexity of O(n), where n represents the array's element count, as the search time is directly linked to the array's size.

    Space Complexity:

    The linear search algorithm has a space complexity of O(1) as it only needs a fixed amount of extra space for storing variables like the index i, the array length n, and the target element x, ensuring that the additional space needed remains constant despite the array's size.

    In summary, the linear search algorithm has a time complexity of O(n) and a space complexity of O(1). It's a straightforward algorithm but not the most efficient for large datasets, as its time complexity grows linearly with the size of the input array.