Homework Answers
7. Order of growth is O(logn) for n size sorted array
8. Linear search required O(n) time and For binary search 1st we need to sort array and then go for binary search hence it take O( n log n (insertion/selection sort)+log n)= n log n . hence linear search is better then binary search in the case of unsorted array.
9) In linear search it take n*k times, in the case of binary search for sorting it take O(n log n) times and then for getting k number of element it take log n time hence total time become O(n log n + k log n)=n log n. so here O(n*k)>O(n log n). so binary search is better than linear search
Add Answer to:
Discrete Mathematics
Unsorted and Sorted Lists For linear search there was no requirement for the list...
2. Here is a sorting algorithm that I like to use. Given an unsorted list of...
2. Here is a sorting algorithm that I like to use. Given an unsorted list of size n, let Xx represent the data in location k of the unsorted list. Compare xi to X2 and switch if necessary so that they are in sorted order, smallest first. Compare Xn-1 and Xn and switch if necessary so that they are in sorted order, smallest first. • Compare x3 with its left neighbors, switching if necessary so that the 3 first entries...
C++ Chapters 3 and 4 discuss sorted and unsorted linear lists. In each of the text...
C++ Chapters 3 and 4 discuss sorted and unsorted linear lists. In each of the text examples, the program begins with an empty list, data is added and manipulated, and the program ends freeing the data. Suggest ideas for dealing with list data that would have more permanence and be stored and retrieved as needed. Use code fragments to illustrate your response.
9. When we have two sorted lists of numbers in non-descending order, and we need to...
9. When we have two sorted lists of numbers in non-descending order, and we need to merge them into one sorted list, we can simply compare the first two elements of the lists, extract the smaller one and attach it to the end of the new list, and repeat until one of the two original lists become empty, then we attach the remaining numbers to the end of the new list and it's done. This takes linear time. Now, try...
When we have two sorted lists of numbers in non-descending order, and we need to merge...
When we have two sorted lists of numbers in non-descending order, and we need to merge them into one sorted list, we can simply compare the first two elements of the lists, extract the smaller one and attach it to the end of the new list, and repeat until one of the two original lists become empty, then we attach the remaining numbers to the end of the new list and it's done. This takes linear time. Now, try to...
Interfaces 1. What is inside an interface definition? What does a class do to an interface...
Interfaces 1. What is inside an interface definition? What does a class do to an interface and what keyword is involved? How does a class do this to an interface (what should we find in the class)? Can an interface have a generic parameter? How do you instantiate an interface as an object? What methods can’t you use on an interface type? Abstract Data Types 2. What does an ADT define? Does an ADT specify programming language and/or data structures...
Full and complete answer in order to get credit. Thank you. Suppose you are given an...
Full and complete answer in order to get credit. Thank you. Suppose you are given an unsorted list of n distinct numbers. However, the list is close to being sorted in the sense that each number is at most k positions away from its original position in the sorted list. For example, suppose the sorted list is in ascending order, then the smallest element in the original list will lie between position 1 and position k + 1, as position...
Using Arrays with Sorting and Searching Algorithms 1) This program has six required outputs and involves...
Using Arrays with Sorting and Searching Algorithms 1) This program has six required outputs and involves searching and sorting an array of integers. Write a java application that initializes an array with the following numbers, in this order: 23, 17, 5, 90, 12, 44, 38, 84, 77, 3, 66, 55, 1, 19, 37, 88, 8, 97, 25, 50, 75, 61, and 49. Then display the unsorted values. This is required output #1 of 6 for this program. 2) Using a...
Puodace a char showing the number of moves required to solve the Towers of Hanoi puzle using t 30...
Puodace a char showing the number of moves required to solve the Towers of Hanoi puzle using t 30. What is an execution frame? What is an activation record? What is contained in it? 31. Write a recursive Java method that computes the factorial of a number 2. Linear search may require up to comparisons while binary search will only require roughly comparisons 33. Sort sorts a list of values by repetitively putting a particular value into its final, sorted,...
Need help with program. I'm stuck Objectives: In this assignment, we will practice manipulating lists of...
Need help with program. I'm stuck
Objectives: In this assignment, we will
practice manipulating lists of data and arranging items in an
ascending/descending order. you will also explore storing
lists/arrays using different sorting algorithms including, the
selection sort, bubble sort, and insertion sort algorithm.
Comparison between the three algorithms are made based on the
number of comparisons and item assignments (basic operations) each
algorithms executes.
Background: Ordering the elements of a list is
a problem that occurs in many computer...
All those points need to be in the code Project 3 Iterative Linear Search, Recursive Binary...
All those points need to be in the code
Project 3 Iterative Linear Search, Recursive Binary Search, and Recursive Selection Sort Class River describes river's name and its length in miles. It provides accessor methods (getters) for both variables, toString() method that returns String representation of the river, and method isLong() that returns true if river is above 30 miles long and returns false otherwise. Class CTRivers describes collection of CT rivers. It has no data, and it provides the...
2. Here is a sorting algorithm that I like to use. Given an unsorted list of size n, let Xx represent the data in location k of the unsorted list. Compare xi to X2 and switch if necessary so that they are in sorted order, smallest first. Compare Xn-1 and Xn and switch if necessary so that they are in sorted order, smallest first. • Compare x3 with its left neighbors, switching if necessary so that the 3 first entries...
9. When we have two sorted lists of numbers in non-descending order, and we need to merge them into one sorted list, we can simply compare the first two elements of the lists, extract the smaller one and attach it to the end of the new list, and repeat until one of the two original lists become empty, then we attach the remaining numbers to the end of the new list and it's done. This takes linear time. Now, try...
Puodace a char showing the number of moves required to solve the Towers of Hanoi puzle using t 30. What is an execution frame? What is an activation record? What is contained in it? 31. Write a recursive Java method that computes the factorial of a number 2. Linear search may require up to comparisons while binary search will only require roughly comparisons 33. Sort sorts a list of values by repetitively putting a particular value into its final, sorted,...
Need help with program. I'm stuck
Objectives: In this assignment, we will
practice manipulating lists of data and arranging items in an
ascending/descending order. you will also explore storing
lists/arrays using different sorting algorithms including, the
selection sort, bubble sort, and insertion sort algorithm.
Comparison between the three algorithms are made based on the
number of comparisons and item assignments (basic operations) each
algorithms executes.
Background: Ordering the elements of a list is
a problem that occurs in many computer...
All those points need to be in the code
Project 3 Iterative Linear Search, Recursive Binary Search, and Recursive Selection Sort Class River describes river's name and its length in miles. It provides accessor methods (getters) for both variables, toString() method that returns String representation of the river, and method isLong() that returns true if river is above 30 miles long and returns false otherwise. Class CTRivers describes collection of CT rivers. It has no data, and it provides the...
Most questions answered within 3 hours.
-
From the literature (reference your sources): What are the
lattice parameters of calcite and aragonite? Why...
asked 37 minutes ago -
Your system is rejecting the question am asking which is
preceded by a case study. It...
asked 41 minutes ago -
3. On January 2, 2000, Larry creates a trust with himself as
trustee. Larry as trustee...
asked 38 minutes ago -
A member of the volleyball team spikes the ball. During this
process, she changes the velocity...
asked 45 minutes ago -
Are adult gamers less likely to use a gaming console (Xbox,
PlayStation, Wii, etc...) than teen...
asked 1 hour ago -
The University of
Texas recently reported that 43% of college students aged 18-24
would spend their...
asked 1 hour ago -
The length of stay at a specific emergency department in
Phoenix, Arizona, in 2009 had a...
asked 1 hour ago -
. Please give the mechanism for this type of problem. Step by
Step
The toxin that...
asked 1 hour ago -
If you have a 1M stock solution and you want to dilute 1 :10
with water,...
asked 1 hour ago -
In a load instruction, the effective address is obtained by
A) Retriving the address from a...
asked 1 hour ago -
Use the following information to answer this question.
Windswept, Inc. 2017 Income Statement ($ in millions)...
asked 1 hour ago -
A mutual fund salesperson has arranged to call on four people
tomorrow. Based on past experience...
asked 1 hour ago