Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Short Answer

a.) Describe the linear search and binary search algorithm for finding an integer in a list of integers in increasing order.

b.) Compare the worst-case time complexities of these two algorithms.

c.) Is one of these algorithms always faster than the other (measured in terms of comparisons)?

a.) Linear search searches for the integer by comparing the integer with the first element in the list, then with the second element, then the third and so on. If the element is found, then the algorithm stops and the position of the element is returned.

b.) Linear: $O (n)$

Binary: $O (\log_{n})$

c.) No

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step 1: a.) Describe the linear search and binary search algorithm for finding an integer in a list of integers in increasing order.

a.) Linear search searches for the integer by comparing the integer with the first element in the list, then with the second element, then the third so on. If the element is found, then the algorithm stops and the position of the element is returned.

Binary search divides the list of integers in two halves. It determines in which half the integer needs to lie (using the increasing order of the initial list) and then the half becomes the new list of the integers. We then divide the list in half again and again determine in which half of the integer lies, which then becomes the new list. This is repeated until the list contains only 1 value. If this value is the integer that we are looking for, the position is returned, else 0 is returned (indicating that the element is not in the list)

Step 2: b.) Compare the worst-case time complexities of these two algorithms.

b.) Linear search in worst case, the integer is not in the list or is the last element in the list, then every element of the list needs to get searched. If the list contains n elements, then we thus make n comparisons and n is $O (n)$

Binary search always executes the algorithm until the list only contains 1 element. Since in every iteration, the list is divide in half, the number of iterations x is such that $2^{x} \geq n$ and thus $x = [\log_{2} n]$ . Finally 1 more comparison is made (to determine if the remaining element in the list is also the element that we are looking for) and thus in total there are $⌈\log_{2} n⌉ + 1$ comparisons, while $⌈\log_{2} n⌉ + 1$ is $O (\log_{n})$

Step 3: c.) Is one of these algorithms always faster than the older (measured in terms of comparisons)?

c.) One algorithm is not always faster than the other algorithm

For example, if the list contains elements.

Binary search then requires only 3 comparisons (twice dividing in half and then check the remaining element in the list)

However, linear search requires only 1 comparison, if the element for which we are looking is the first element in the list, and linear search requires 4 comparisons, if the element for which we are looking is the last element in the list.

Thus linear search could be faster or slower than binary search.

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

a.) Describe the linear search and binary search algorithm for finding an integer in a list of integers in increasing order.

b.) Compare the worst-case time complexities of these two algorithms.

c.) Is one of these algorithms always faster than the other (measured in terms of comparisons)?

Step by Step Solution

Step 1: a.) Describe the linear search and binary search algorithm for finding an integer in a list of integers in increasing order.

Step 2: b.) Compare the worst-case time complexities of these two algorithms.

Step 3: c.) Is one of these algorithms always faster than the older (measured in terms of comparisons)?

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

a.) Describe the linear search and binary search algorithm for finding an integer in a list of integers in increasing order. b.) Compare the worst-case time complexities of these two algorithms. c.) Is one of these algorithms always faster than the other (measured in terms of comparisons)?

Step by Step Solution

Step 1: a.) Describe the linear search and binary search algorithm for finding an integer in a list of integers in increasing order.

Step 2: b.) Compare the worst-case time complexities of these two algorithms.

Step 3: c.) Is one of these algorithms always faster than the older (measured in terms of comparisons)?

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths

a.) Describe the linear search and binary search algorithm for finding an integer in a list of integers in increasing order.

b.) Compare the worst-case time complexities of these two algorithms.

c.) Is one of these algorithms always faster than the other (measured in terms of comparisons)?