Skip to main content

Linear Search Quiz Solutions

  1. What is Linear Search?

    • A) A search algorithm that repeatedly divides the search interval in half
    • B) A search algorithm that checks every element sequentially until the target is found or the list ends
    • C) A search algorithm that only works on sorted arrays
    • D) A search algorithm that uses a hash function to locate elements
      Answer: B) A search algorithm that checks every element sequentially until the target is found or the list ends
      Explanation: Linear search examines each element of a list one by one, in order, comparing it to the target value, until a match is found or the entire list has been checked.

  2. Does Linear Search require the input array to be sorted?

    • A) Yes, it only works on sorted arrays
    • B) No, it works on both sorted and unsorted data
    • C) Yes, but only for numeric data
    • D) No, but it only works on sorted strings
      Answer: B) No, it works on both sorted and unsorted data
      Explanation: Unlike binary search, linear search does not rely on any ordering of elements. It checks each element sequentially, so it works correctly on both sorted and unsorted data.

  3. What is the time complexity of Linear Search in the worst case?

    • A) O(1)
    • B) O(log n)
    • C) O(n)
    • D) O(n²)
      Answer: C) O(n)
      Explanation: In the worst case (target is the last element or not present at all), linear search must examine every one of the n elements, giving a time complexity of O(n).

  4. What is the best-case time complexity of Linear Search?

    • A) O(n)
    • B) O(log n)
    • C) O(1)
    • D) O(n²)
      Answer: C) O(1)
      Explanation: The best case occurs when the target element is found at the very first position checked, requiring only a single comparison — O(1) time.

  5. Which of these is a practical use case where Linear Search would be appropriate?

    • A) Searching a huge sorted database with millions of records
    • B) Searching a small, unsorted list of items, such as checking if a value exists in a short array
    • C) Finding the median of a sorted dataset
    • D) Performing range queries on a balanced tree
      Answer: B) Searching a small, unsorted list of items, such as checking if a value exists in a short array
      Explanation: Linear search is best suited for small datasets or unsorted data, where the overhead of sorting or building an index would outweigh the simplicity of just scanning each element directly.

  6. What is the average-case time complexity of Linear Search, assuming the target is equally likely to be at any position (or absent)?

    • A) O(1)
    • B) O(n)
    • C) O(log n)
    • D) O(n log n)
      Answer: B) O(n)
      Explanation: On average, assuming a uniform probability distribution, the algorithm examines roughly n/2 elements before finding the target (or n elements if the search may fail), which is still O(n) asymptotically.

  7. What is the space complexity of a standard iterative Linear Search implementation?

    • A) O(n)
    • B) O(log n)
    • C) O(1)
    • D) O(n²)
      Answer: C) O(1)
      Explanation: Linear search only needs a constant amount of extra space (e.g., a loop index variable) regardless of input size, making its space complexity O(1).

  8. How does Linear Search's time complexity compare to Binary Search for a sorted array of n elements?

    • A) Linear search is O(log n), faster than binary search's O(n)
    • B) Linear search is O(n) in the worst case, while binary search achieves O(log n) on sorted data
    • C) Both have identical O(n) complexity in all cases
    • D) Binary search is always slower regardless of data size
      Answer: B) Linear search is O(n) in the worst case, while binary search achieves O(log n) on sorted data
      Explanation: When data is sorted, binary search's divide-and-conquer approach achieves O(log n) — far faster than linear search's O(n) for large datasets. However, binary search requires sorted input, while linear search does not.

  9. In a 'Sentinel Linear Search' optimization, what technique is used to reduce the number of comparisons per iteration?

    • A) Sorting the array first
    • B) Placing the target value at the end of the array as a sentinel, eliminating the need for an explicit bounds check each iteration
    • C) Searching from both ends simultaneously
    • D) Using a hash table internally
      Answer: B) Placing the target value at the end of the array as a sentinel, eliminating the need for an explicit bounds check each iteration
      Explanation: Sentinel linear search temporarily places the search key at the end of the array. This removes the need to check 'have we reached the end of the array?' on every iteration — only a single equality check is needed per loop, reducing constant-factor overhead (though asymptotic complexity remains O(n)).

  10. If you need to perform Linear Search repeatedly (many times) on the same static dataset, what is a better long-term strategy and why?

  • A) Keep using linear search every time, since no alternative exists
  • B) Pre-process the data once (e.g., sort it for binary search, or build a hash table for O(1) average lookups) to amortize the one-time cost across many faster subsequent searches
  • C) Linear search is always optimal regardless of query frequency
  • D) Convert the data into a linked list to speed up search
    Answer: B) Pre-process the data once (e.g., sort it for binary search, or build a hash table for O(1) average lookups) to amortize the one-time cost across many faster subsequent searches
    Explanation: When search is performed many times on largely static data, investing in preprocessing (sorting for O(log n) binary search, or hashing for O(1) average lookups) pays off because the one-time cost is amortized over many fast queries — unlike linear search's repeated O(n) cost each time.
  1. What is the lower bound (worst-case comparisons) proven for any comparison-based search algorithm on an arbitrary unsorted array of n elements, and how does Linear Search relate to it?
  • A) Ω(log n); linear search is asymptotically suboptimal
  • B) Ω(n); linear search is asymptotically optimal for unsorted data since every element may need to be inspected
  • C) Ω(1); any search algorithm can theoretically solve this in constant time
  • D) Ω(n²); no algorithm can do better than quadratic time
    Answer: B) Ω(n); linear search is asymptotically optimal for unsorted data since every element may need to be inspected
    Explanation: For an arbitrary unsorted array, no algorithm can guarantee finding (or ruling out) a target without potentially inspecting every element in the worst case — this gives a lower bound of Ω(n). Linear search achieves this bound, making it asymptotically optimal for unsorted data, even though faster average-case heuristics may exist for specific data distributions.
  1. In parallel computing, how can Linear Search be adapted to take advantage of multiple processors, and what complexity can be achieved?
  • A) It cannot be parallelized under any circumstances
  • B) By dividing the array into p segments and searching each segment concurrently on a separate processor, achieving O(n/p) time with p processors
  • C) Parallelization always makes linear search slower
  • D) Parallel linear search achieves O(log n) regardless of processor count
    Answer: B) By dividing the array into p segments and searching each segment concurrently on a separate processor, achieving O(n/p) time with p processors
    Explanation: Linear search parallelizes naturally: split the array into p roughly equal segments, assign each to a separate processor, and have all processors search concurrently. The overall time becomes O(n/p) (ignoring synchronization overhead), demonstrating near-linear speedup with additional processors — though this requires coordination to report which processor found the result.