CS251 - Data Structures - Chapter 1 - Search & Sorting Algorithms

Question 1

Algorithm

Answer 1

is a sequence of steps for accomplishing a task

Question 2

Linear Search

Answer 2

is a search algorithm that starts from the beginning of a list, and checks each element until the search key is found or the end of the list is reached. Usually implemented in a simple for loop which checks each element one-by-one

Question 3

Runtime

Answer 3

An algorithm’s runtime is the time the algorithm takes to execute. If each comparison takes 1 µs (1 microsecond), a linear search algorithm’s runtime is up to 1 s to search a list with 1,000,000 elements, 10 s for 10,000,000 elements, and so on. Ex: Searching Amazon’s online store, which has more than 200 million items, could require more than 3 minutes.

An algorithm typically uses a number of steps proportional to the size of the input. For a list with 32 elements, linear search requires at most 32 comparisons: 1 comparison if the search key is found at index 0, 2 if found at index 1, and so on, up to 32 comparisons if the the search key is not found. For a list with N elements, linear search thus requires at most N comparisons. The algorithm is said to require “on the order” of N comparisons.