We are using sequential search to search an array of size n. It is known that...
We are using sequential search to search an array of size n. It is known that the item we are looking is definitely present in the array. The probability that the item we are looking for is the last one in the array is 1/3. The probabilities of all other items are equal. What is the average case time complexity(counting the number of comparisons) of the algorithm in this case?
Homework Answers
`Hey,
Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.
Since array has length n
So, Expected time is
(1/3)*n+(2/(3*(n-1)))*((n-1)+(n-2)+.....1)
E=n/3+(n*(n-1))/(3*(n-1))=n/3+n/3=2n/3
So, Expected time is
2n/3
Kindly revert for any queries
Thanks.
Add Answer to:
We are using sequential search to search an array of size n. It
is known that...
Using Sequential Search on an array of size n, the probability that the search key is...
Using Sequential Search on an array of size n, the probability that the search key is not present in the array is 1/4. The probabilities of matching the key to any of the n items in the array are all equal. What is the average case complexity function for the Sequential Search under these conditions? If we know that our system can execute one basic operation in 8 nanoseconds, what will be the estimated running times of Sequential Search under...
Preview File Edit View Go Tools Window Help Homework_6.pdf (1 page) Homework_5.pdf pagal 2. An array...
Preview File Edit View Go Tools Window Help Homework_6.pdf (1 page) Homework_5.pdf pagal 2. An array of n distinct integers is to be searched using Sequential Search. The probability that the search key matches the last item in the array is y, and the probability that the item searched for is not present in the array is likewise y. The probabilities of matching the 19through (n-1)"items are all equal. What is the average case time complexity, A(n), where the basic...
Consider an ordered array A of size n and the following ternary search algorithm for finding...
Consider an ordered array A of size n and the following ternary search algorithm for finding the index i such that A[i] = K. Divide the array into three parts. If A[n/3] > K. the first third of the array is searched recursively, else if A[2n/3] > K then the middle part of the array is searched recursively, else the last thud of the array is searched recursively. Provisions are also made in the algorithm to return n/3 if A[n/3]...
Here is the initial adjacency matrix W for the Floyd algorithm. What is the value of...
Here is the initial adjacency matrix W for the Floyd algorithm. What is the value of D(1)[5][2]? 12345 103582 2607912 3940111 432902 527380 In Binary Search, if we assume that the item matching the search key is definitely present in the array and that the probabilities of matching the search key to any of the items are all equal, the average case complexity function is in Theta of: Select one: a. log n b. n. c. n log n d....
We know that binary search on a sorted array of size n takes O(log n) time....
We know that binary search on a sorted array of size n takes O(log n) time. Design a similar divide-and-conquer algorithm for searching in a sorted singly linked list of size n. Describe the steps of your algorithm in plain English. Write a recurrence equation for the runtime complexity. Solve the equation by the master theorem.
Language = c++ Write a program to find the number of comparisons using the binary search...
Language = c++ Write a program to find the number of comparisons using the binary search and sequential search algorithms as follows: o Suppose list is an array of 1000 elements. o Use a random number generator to fill the list. o Use the function insertOrd to initially insert all the elements in the list. o You may use the following function to fill the list: void fill(orderedArrayListType& list) { int seed = 47; int multiplier = 2743; ...
4) [15 points total (5 points each)] Assume you are given a sorted array A of n numbers, where A is indexed from 1 up t...
4) [15 points total (5 points each)] Assume you are given a sorted array A of n numbers, where A is indexed from 1 up to n, anda number num which we wish to insert into A, in the proper sorted position. The function Search finds the minimum index i such that num should be inserted into Ali]. It searches the array sequentially until it finds the location i. Another function MakeRoom moves A[i], .., AIn] to Ali+1]...AIn+1] same sort...
Suppose that, even unrealistically, we are to search a list of 700 million items using Binary...
Suppose that, even unrealistically, we are to search a list of
700 million items using Binary Search, Recursive (Algorithm 2.1).
What is the maximum number of comparisons that this algorithm must
perform before finding a given item or concluding that it is not in
the list
“Suppose that, in a divide-and-conquer algorithm, we always
divide an instance of size n of a problem into n subinstances of
size n/3, and the dividing and combining steps take linear time.
Write a...
The purpose of this assignment is to familiarize you with sort algorithms. Problem Description is as follows: 8. Search Benchmarks Write a program that has at least 20 250 integers stored in an ar...
The purpose of this assignment is to familiarize you with sort algorithms. Problem Description is as follows: 8. Search Benchmarks Write a program that has at least 20 250 integers stored in an array in ascending order. It should call a function that uses the linear search algorithm to locate one of the values. The function should keep a count of the number of comparisons it makes until it finds the value. The program then should call a function that...
C++ Sorting and Searching 1. Mark the following statements as true or false. a. A sequential...
C++ Sorting and Searching 1. Mark the following statements as true or false. a. A sequential search of a list assumes that the list elements are sorted in ascending order. b. A binary search of a list assumes that the list is sorted. 2. Consider the following list: 63 45 32 98 46 57 28 100 Using a sequential search, how many comparisons are required to determine whether the following items are in the list or not? (Recall that comparisons...
Preview File Edit View Go Tools Window Help Homework_6.pdf (1 page) Homework_5.pdf pagal 2. An array of n distinct integers is to be searched using Sequential Search. The probability that the search key matches the last item in the array is y, and the probability that the item searched for is not present in the array is likewise y. The probabilities of matching the 19through (n-1)"items are all equal. What is the average case time complexity, A(n), where the basic...
Consider an ordered array A of size n and the following ternary search algorithm for finding the index i such that A[i] = K. Divide the array into three parts. If A[n/3] > K. the first third of the array is searched recursively, else if A[2n/3] > K then the middle part of the array is searched recursively, else the last thud of the array is searched recursively. Provisions are also made in the algorithm to return n/3 if A[n/3]...
Here is the initial adjacency matrix W for the Floyd algorithm. What is the value of D(1)[5][2]? 12345 103582 2607912 3940111 432902 527380 In Binary Search, if we assume that the item matching the search key is definitely present in the array and that the probabilities of matching the search key to any of the items are all equal, the average case complexity function is in Theta of: Select one: a. log n b. n. c. n log n d....
4) [15 points total (5 points each)] Assume you are given a sorted array A of n numbers, where A is indexed from 1 up to n, anda number num which we wish to insert into A, in the proper sorted position. The function Search finds the minimum index i such that num should be inserted into Ali]. It searches the array sequentially until it finds the location i. Another function MakeRoom moves A[i], .., AIn] to Ali+1]...AIn+1] same sort...
Suppose that, even unrealistically, we are to search a list of
700 million items using Binary Search, Recursive (Algorithm 2.1).
What is the maximum number of comparisons that this algorithm must
perform before finding a given item or concluding that it is not in
the list
“Suppose that, in a divide-and-conquer algorithm, we always
divide an instance of size n of a problem into n subinstances of
size n/3, and the dividing and combining steps take linear time.
Write a...
Most questions answered within 3 hours.
-
A monopoly sells in two countries . The demand curves in the two
countries are p1...
asked 21 minutes ago -
A .15kg rubber ball is bounced off a wall. Before hitting the
wall, the ball moves...
asked 1 hour ago -
A manufacturing company preparing to build a new plant is
considering three potential locations for it....
asked 1 hour ago -
B. If compound Y has approximately the same values of solubility
in toluene as compound X,...
asked 1 hour ago -
Oscar Inc. has inventory in Japan valued at 39,051,000 Yen one
year ago. One year ago...
asked 1 hour ago -
If Canada suffered from "fundamental disequilibrium," and its
government choose not to devalue its currency, a...
asked 2 hours ago -
4. How many input & output Key Value Pairs are passed into,
and emitted out of...
asked 1 hour ago -
Why would your heart not function well if constructed of
skeletal muscle? What is the particular...
asked 2 hours ago -
Please respond to this essay question in full essay form for
Chemistry 1102 Organic and Biochemistry:...
asked 2 hours ago -
Determine the head loss and velocity of flow in a water supply main
of 15.0 cm...
asked 2 hours ago -
A marketing executive who knowingly authorizes a shoddy
defective product to be brought to market is...
asked 2 hours ago -
Write a psudocode:
1. Define a function called authorize that takes in 2 strings,
uName, and...
asked 2 hours ago