Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 2: 18 E (page 85)

Consider the task of searching a sorted array A[1,…,n] for a given element x: a task we usually perform by binary search in time O(logn) . Show that any algorithm that accesses the array only via comparisons (that is, by asking questions of the form “is A[i]≤z 0?”), must take Ω(logn) steps.

Short Answer

Expert verified

Yes, any algorithm that accesses the array only via comparisons take Ωlogn steps.

Step by step solution

01

Explain Binary Search

Binary search is implemented on a sorted array. Binary search always starts with the mid element. Mid element compared with every other element and the element to be searched will be found.

02

Show that any algorithm that accesses the array via comparisons takes Ω(logn) steps.

Knowing that a query produces two kinds of results that is yes or no. The arrayA1,…,ncan be divided into two parts based on the result of the query.

In the best case, the two divided parts will be equal and the search can be scaled regardless of the query result.

Therefore, To locate a unique element by comparisons, it takes Ωlogn steps

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

You are given an array of nelements, and you notice that some of the elements are duplicates; that is, they appear more than once in the array. Show how to remove all duplicates from the array in time O(nlogn) .

This problem illustrates how to do the Fourier Transform (FT) in modular arithmetic, for example, modulo .(a) There is a number such that all the powers ω,ω2,...,ω6 are distinct (modulo ). Find this role="math" localid="1659339882657" ω, and show that ω+ω2+...+ω6=0. (Interestingly, for any prime modulus there is such a number.)

(b) Using the matrix form of the FT, produce the transform of the sequence (0,1,1,1,5,2) modulo 7; that is, multiply this vector by the matrix M6(ω), for the value of ωyou found earlier. In the matrix multiplication, all calculations should be performed modulo 7.

(c) Write down the matrix necessary to perform the inverse FT. Show that multiplying by this matrix returns the original sequence. (Again all arithmetic should be performed modulo 7.)

(d) Now show how to multiply the polynomials and using the FT modulo 7.

Find the unique polynomial of degree 4 that takes on values p(1)=2,p(2)=1,p(3)=0,p(4)=4,andp(5)=0. Write your answer in the coefficient representation.

A binary tree is full if all of its vertices have either zero or two children. Let Bndenote the number of full binary trees with n vertices. (a)By drawing out all full binary trees with 3, 5, or 7 vertices, determine the exact values of B3, B5, and B7. Why have we left out even numbers of vertices, like B4?

(b) For general n, derive a recurrence relation for Bn.

(c) Show by induction that Bnis Ω(2n).

An array A[1...n] is said to have a majority element if more than half of its entries are the same. Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element, and, if so, to find that element. The elements of the array are not necessarily from some ordered domain like the integers, and so there can be no comparisons of the form “ is A[i]>A[j] ?”. (Think of the array elements as GIF files, say.) However you can answer questions of the form: “is ..?” in constant time.

(a) Show how to solve this problem in O(nlogn) time. (Hint: Split the array A into two arrays A1and A2of half the size. Does knowing the majority elements of A1and A2help you figure out the majority element of A? If so, you can use a divide-and-conquer approach.)

(b) Can you give a linear-time algorithm? (Hint: Here’s another divide-and-conquer approach:• Pair up the elements of A arbitrarily, to get n/2 pairs• Look at each pair: if the two elements are different, discard both of them; if they are the same, keep just one of them . Show that after this procedure there are at most n/2 elements left, and that they have a majority element if A does.)
See all solutions

Recommended explanations on Computer Science Textbooks

Computer Programming

Read Explanation

Game Design in Computer Science

Read Explanation

Data Structures

Read Explanation

Big Data

Read Explanation

Problem Solving Techniques

Read Explanation

Data Representation in Computer Science

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free